[BZOJ2599][IOI2011]Race 點分治

2599: [IOI2011]Race

Time Limit:?70 Sec??Memory Limit:?128 MB
Submit:?3934??Solved:?1163
[Submit][Status][Discuss]

Description

給一棵樹,每條邊有權.求一條簡單路徑,權值和等于K,且邊的數量最小.N <= 200000, K <= 1000000

Input

第一行兩個整數 n, k
第二..n行每行三個整數表示一條無向邊的兩端和權值 (注意點的編號從0開始)

Output

一個整數表示最小邊數量如果不存在這樣的路徑輸出-1

Sample Input

4 3
0 1 1
1 2 2
1 3 4

Sample Output

考慮點分治，每次對子樹進行dfs求出子樹中每個點到根的距離并記在dis[i]中，步數記在b[i]中。

同時我們開一個桶tot，記錄這顆子樹之前的子樹中所有dis中步數的最小值。

開一個v的桶記錄此時tot桶中記錄的數是否為以當前u為根更新的答案。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 using namespace std;
 7 struct data {
 8     int to,next,val;
 9 }e[400005];
10 int head[200005],cnt;
11 bool vis[200005];
12 void add(int u,int v,int val) {e[cnt].to=v;e[cnt].next=head[u];e[cnt].val=val;head[u]=cnt++;}
13 int son[200005],f[200005],root,sum;
14 int b[200005],dis[200005],tot[1000005];
15 int n,k;
16 int ans=0;
17 int num;
18 int v[1000005];
19 int tt=0;
20 void findroot(int x,int fa) {
21     son[x]=1;f[x]=0;
22     for(int i=head[x];i>=0;i=e[i].next) {
23         int to=e[i].to;if(to==fa||vis[to]) continue;
24         findroot(to,x);
25         son[x]+=son[to];
26         f[x]=max(f[x],son[to]);
27     }
28     f[x]=max(f[x],sum-son[x]);
29     if(f[x]<f[root]) root=x;
30     return;
31 }
32 void dfs(int x,int fa,int d,int dep) {
33     dis[++num]=d;b[num]=dep;
34     for(int i=head[x];i>=0;i=e[i].next) {
35         int to=e[i].to;if(to==fa||vis[to]) continue;
36         if(d+e[i].val>k) continue;
37         dfs(to,x,d+e[i].val,dep+1);
38     }
39 }
40 void work(int x) {
41     vis[x]=1;
42     bool flag=0;
43     for(int i=head[x];i>=0;i=e[i].next) {
44         num=0;
45         int to=e[i].to;if(vis[to]) continue;
46         if(e[i].val>k) continue;
47         dfs(to,x,e[i].val,1);
48         for(int j=1;j<=num;j++) if(dis[j]==k) ans=min(ans,b[j]);
49         if(flag)
50             for(int j=1;j<=num;j++) 
51                 if(dis[j]<=k&&v[k-dis[j]]==x) ans=min(ans,b[j]+tot[k-dis[j]]);
52         for(int j=1;j<=num;j++) 
53             if(dis[j]<=k) {
54                 if(v[dis[j]]!=x) v[dis[j]]=x,tot[dis[j]]=b[j];
55                 else tot[dis[j]]=min(tot[dis[j]],b[j]);
56             }
57         flag=1;
58     }
59     for(int i=head[x];i>=0;i=e[i].next) {
60         int to=e[i].to;
61         if(vis[to]) continue;
62         root=0;f[0]=n;sum=son[to];
63         findroot(to,x);
64         work(root);
65     }
66 }
67 int main() {
68     //freopen("gg.in","r",stdin);
69     memset(head,-1,sizeof(head));
70     scanf("%d%d",&n,&k);
71     for(int i=1;i<n;i++) {
72         int u,v,t;
73         scanf("%d%d%d",&u,&v,&t);
74         add(u+1,v+1,t);add(v+1,u+1,t);
75     }
76     sum=n;ans=n;f[0]=n;
77     findroot(1,0);
78     work(root);
79     if(ans==n) printf("-1");
80     else printf("%d",ans);
81 }

View Code

轉載于:https://www.cnblogs.com/wls001/p/7756381.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/390948.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/390948.shtml
英文地址，請注明出處：http://en.pswp.cn/news/390948.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！