bzoj 2599(点分治)

48 阅读 0 评论 32 点赞

我是靠谱客的博主 危机猫咪，最近开发中收集的这篇文章主要介绍bzoj 2599(点分治)，觉得挺不错的，现在分享给大家，希望可以做个参考。

                                概述
                            
 2599: [IOI2011]Race 
 Time Limit: 70 Sec   
 Memory Limit: 128 MB 
 
 Submit: 2586   
 Solved: 768 
 
 [ 
 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 2
 
 解题思路：数据范围是N:20w, K100w. 点分治, 我们只需考虑经过当前树根的方案. K最大只有100w, 直接开个数组CNT[x]表示与当前树根距离为x的最少边数, 然后就可以对根的子树依次dfs并更新CNT数组和答案. 复杂度是O(NlogN)
 
 #include<cstdio> 
 
 #include<cstring> 
 
 #include<iostream> 
 
 #include<algorithm> 
 
 using 
  namespace 
  std; 
 
 int 
  n,k,len,sug,mx,root,ans,tail,head; 
 
 int 
  to[410000],next[410000],zhi[410000],h[410000]; 
 
 int 
  size[210000],sg[1100000]; 
 
 bool 
  b[210000]; 
 
 struct 
  ss 
 
 { 
 
 int 
  di,zhi; 
 
 }q[210000]; 
 
 const 
  int 
  ll=1000000000;  
 
 inline 
  int 
  read() 
 
 { 
 
 char 
  y;  
 int 
  x=0,f=1; y= 
 getchar 
 (); 
 
 while 
  (y< 
 '0' 
  || y> 
 '9' 
 ) { 
 if 
  (y== 
 '-' 
 ) f=-1; y= 
 getchar 
 ();} 
 
 while 
  (y>= 
 '0' 
  && y<= 
 '9' 
 ) {x=x*10+ 
 int 
 (y)-48; y= 
 getchar 
 ();} 
 
 return 
  x*f; 
 
 }  
 
 void 
  insert( 
 int 
  x, 
 int 
  y, 
 int 
  z)  
 
 { 
 
 ++len; to[len]=y; next[len]=h[x]; zhi[len]=z; h[x]=len; 
 
 } 
 
 void 
  find( 
 int 
  now, 
 int 
  from) 
 
 { 
 
 int 
  pan=-1; 
 
 size[now]=1;  
 int 
  u=h[now]; 
 
 while 
  (u!=0) 
 
 { 
 
 if 
  (to[u]!=from && b[to[u]]) 
 
 { 
 
 find(to[u],now); pan=max(pan,size[to[u]]); 
 
 size[now]+=size[to[u]]; 
 
 } 
 
 u=next[u]; 
 
 } 
 
 pan=max(pan,sug-size[now]); 
 
 if 
  (pan<mx) mx=pan,root=now; 
 
 }  
 
 void 
  dfs( 
 int 
  now, 
 int 
  from, 
 int 
  shu, 
 int 
  step) 
 
 { 
 
 if 
  (shu>k) 
 return 
 ; 
 
 if 
  (shu==k) 
 
 { 
 
 ans=min(ans,step); 
 
 } 
 else 
 
 { 
 
 ans=min(ans,step+sg[k-shu]); 
 
 ++tail; q[tail].zhi=step; q[tail].di=shu;  
 
 } 
 
 int 
  u=h[now]; 
 
 while 
  (u!=0) 
 
 { 
 
 if 
  (to[u]!=from && b[to[u]]) 
 
 { 
 
 dfs(to[u],now,shu+zhi[u],step+1); 
 
 } 
 
 u=next[u]; 
 
 } 
 
 } 
 
 void 
  solve( 
 int 
  now) 
 
 { 
 
 b[now]= 
 false 
 ; 
 
 int 
  u=h[now]; 
 
 tail=head=0; 
 
 while 
  (u!=0) 
 
 { 
 
 if 
  (b[to[u]]) 
 
 dfs(to[u],now,zhi[u],1); 
 
 for 
  ( 
 int 
  i=head+1;i<=tail;++i) 
 
 sg[q[i].di]=min(sg[q[i].di],q[i].zhi); 
 
 head=tail; 
 
 u=next[u]; 
 
 } 
 
 for 
  ( 
 int 
  i=1;i<=tail;++i) 
 
 sg[q[i].di]=ll; 
 
 u=h[now]; 
 
 while 
  (u!=0) 
 
 { 
 
 if 
  (b[to[u]]) 
 
 { 
 
 sug=size[to[u]]; mx=ll; 
 
 find(to[u],-1); 
 
 solve(root); 
 
 } 
 
 u=next[u]; 
 
 } 
 
 } 
 
 int 
  main() 
 
 { 
 
 n=read(); k=read(); 
 
 for 
  ( 
 int 
  i=1;i<=k;++i) 
 
 sg[i]=ll; 
 
 memset 
 (b, 
 true 
 , 
 sizeof 
 (b)); 
 
 for 
  ( 
 int 
  i=1;i<=n-1;++i) 
 
 { 
 
 int 
  x,y,z; 
 
 x=read(); y=read(); z=read(); 
 
 insert(x,y,z); insert(y,x,z); 
 
 } 
 
 ans=ll; 
 
 sug=n; mx=ll, root=-1; 
 
 find(0,-1); 
 
 solve(root); 
 
 if 
  (ans==ll)  
 printf 
 ( 
 "-1" 
 ); 
 else 
  printf 
 ( 
 "%d" 
 ,ans); 
 
 } 

最后以上就是危机猫咪为你收集整理的bzoj 2599(点分治)的全部内容，希望文章能够帮你解决bzoj 2599(点分治)所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。