注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

 
 
 

日志

 
 

树的分治——点分治 模板题 poj 1741 ( bzoj 1468 )  

2014-03-28 08:43:32|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

从qzc那篇论文上看到了这题 然后

找的一份比较易懂的模板按照自己的风格改了下

终于改好了。。。

#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #define rep(i,n) for(int i=1;i<=n;++i) #define imax(x,y) (x>y?x:y) #define imin(x,y) (x<y?x:y) using namespace std; const int N=40010,BIG=1000000000; int firste[N],nexte[N<<1],v[N<<1],w[N<<1]; int sz[N],lim[N],dist[N]; bool vis[N]; int n,e=0,root,tot,md,sum,ans=0; void build_edge(int x,int y,int z) { ++e; nexte[e]=firste[x]; firste[x]=e; v[e]=y; w[e]=z; } void getroot(int u,int fa) { sz[u]=1; lim[u]=0; for(int p=firste[u];p;p=nexte[p]) if(v[p]!=fa&&!vis[v[p]]) { getroot(v[p],u); sz[u]+=sz[v[p]]; lim[u]=imax(lim[u],sz[v[p]]); } lim[u]=imax(lim[u],sum-sz[u]); if(lim[u]<lim[root])root=u; } void getdist(int u,int fa,int d) { dist[++tot]=d; for(int p=firste[u];p;p=nexte[p]) if(v[p]!=fa&&!vis[v[p]]) getdist(v[p],u,d+w[p]); } int calc(int u,int d) { tot=0; getdist(u,0,d); sort(dist+1,dist+1+tot); int res=0; for(int i=1,j=tot;i<j;) { if(dist[i]+dist[j]<=md){res+=j-i;++i;} else --j; } return res; } void getans(int u) { ans+=calc(u,0); vis[u]=1; for(int p=firste[u];p;p=nexte[p]) if(!vis[v[p]]) { ans-=calc(v[p],w[p]); sum=sz[v[p]]; lim[0]=sum; root=0; getroot(v[p],0); getans(root); } } int main() { int a,b,c; scanf("%d",&n); for(int i=1;i<n;++i) { scanf("%d%d%d",&a,&b,&c); build_edge(a,b,c); build_edge(b,a,c); } scanf("%d",&md); root=0; lim[0]=n; sum=n; getroot(1,0); getans(root); printf("%d",ans); return 0; }


  评论这张
 
阅读(212)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017