首页 > 代码库 > BZOJ2599: [IOI2011]Race
BZOJ2599: [IOI2011]Race
2599: [IOI2011]Race
Time Limit: 50 Sec Memory Limit: 128 MBSubmit: 1401 Solved: 412
[Submit][Status]
Description
给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小.
Input
第一行 两个整数 n, k
第二..n行 每行三个整数 表示一条无向边的两端和权值 (注意点的编号从0开始)
Output
一个整数 表示最小边数量 如果不存在这样的路径 输出-1
Sample Input
4 3
0 1 1
1 2 2
1 3 4
0 1 1
1 2 2
1 3 4
Sample Output
2
题解：
居然1A了，还跑这么快233.。。。
有关树上路径我们可以考虑点分治。
假如我们当前正在处理以rt为根的树，那么路径统计的时候比较麻烦的就是在同一棵子树内的两个点。用g[i]表示达到i距离最小边数。
处理这个问题很简单，我们可以先用一棵子树的信息来更新答案，再用它的信息来更新我们的g数组。
就是这样，最后再做一遍还原即可。
inline void work(int x){ v[x]=1; for(int i=head[x],y;i;i=e[i].next)if(!v[y=e[i].go]) { cnt=0; getdep(y,x,e[i].w,1); for1(j,cnt)if(d[j][0]<=k)ans=min(ans,g[k-d[j][0]]+d[j][1]); for1(j,cnt)if(d[j][0]<=k)g[d[j][0]]=min(g[d[j][0]],d[j][1]); } ans=min(ans,g[k]); for(int i=head[x],y;i;i=e[i].next)if(!v[y=e[i].go]) { cnt=0; getdep(y,x,e[i].w,1); for1(j,cnt)if(d[j][0]<=k)g[d[j][0]]=inf; } for(int i=head[x],y;i;i=e[i].next)if(!v[y=e[i].go]) { sum=s[y];rt=0; getrt(y,x); work(rt); }}
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 200000+5 26 27 #define maxm 2000000+5 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 struct edge{int go,next,w;}e[2*maxn]; 61 int n,k,cnt,tot,sum,rt,ans=inf,f[maxn],g[maxm],d[maxn][2],head[maxn],s[maxn]; 62 bool v[maxn]; 63 inline void insert(int x,int y,int z) 64 { 65 e[++tot]=(edge){y,head[x],z};head[x]=tot; 66 e[++tot]=(edge){x,head[y],z};head[y]=tot; 67 } 68 inline void getrt(int x,int fa) 69 { 70 s[x]=1;f[x]=0; 71 for(int i=head[x],y;i;i=e[i].next)if(!v[y=e[i].go]&&y!=fa) 72 { 73 getrt(y,x); 74 s[x]+=s[y]; 75 f[x]=max(f[x],s[y]); 76 } 77 f[x]=max(f[x],sum-f[x]); 78 if(f[x]<f[rt])rt=x; 79 } 80 inline void getdep(int x,int fa,int w1,int w2) 81 { 82 d[++cnt][0]=w1;d[cnt][1]=w2; 83 for(int i=head[x],y;i;i=e[i].next)if(!v[y=e[i].go]&&y!=fa)getdep(y,x,w1+e[i].w,w2+1); 84 } 85 inline void work(int x) 86 { 87 v[x]=1; 88 for(int i=head[x],y;i;i=e[i].next)if(!v[y=e[i].go]) 89 { 90 cnt=0; 91 getdep(y,x,e[i].w,1); 92 for1(j,cnt)if(d[j][0]<=k)ans=min(ans,g[k-d[j][0]]+d[j][1]); 93 for1(j,cnt)if(d[j][0]<=k)g[d[j][0]]=min(g[d[j][0]],d[j][1]); 94 } 95 ans=min(ans,g[k]); 96 for(int i=head[x],y;i;i=e[i].next)if(!v[y=e[i].go]) 97 { 98 cnt=0; 99 getdep(y,x,e[i].w,1);100 for1(j,cnt)if(d[j][0]<=k)g[d[j][0]]=inf;101 }102 for(int i=head[x],y;i;i=e[i].next)if(!v[y=e[i].go])103 {104 sum=s[y];rt=0;105 getrt(y,x);106 work(rt);107 }108 }109 110 int main()111 112 {113 114 freopen("input.txt","r",stdin);115 116 freopen("output.txt","w",stdout);117 118 n=read();k=read();119 for0(i,k)g[i]=inf;120 for1(i,n-1)121 {122 int x=read()+1,y=read()+1,z=read();insert(x,y,z);123 }124 f[rt=0]=inf;125 sum=n;126 getrt(1,0);127 work(rt);128 if(ans>=n)ans=-1;129 cout<<ans<<endl;130 131 return 0;132 133 }
BZOJ2599: [IOI2011]Race
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。