Poj 1741 Tree

2019-11-08 19:26:51

字体：大中小

来源：转载

供稿：网友

传送门

http://poj.org/PRoblem?id=1741

题目大意

给出一颗n $n$ 个节点，n−1 $n-1$ 条边的树，询问两点(u,v) $(u,v)$ 满足起简单路径的长度小于等于k $k$ 的方案数，k $k$ 为给定常数。

我的想法

考虑一颗树，那么(u,v) $(u,v)$ 有两种可能：要么过树根，要么不过树根x $x$ 。考虑点分治，如果过x $x$ 的话直接递归就好了；不过x $x$ 呢，我们可以把所有点到x $x$ 的距离d(u,x) $d(u,x)$ 算出来，如果存在两个点(u,v) $(u,v)$ 满足dis(u,x)+dis(v,x)≤k $dis(u,x)+dis(v,x)/leq k$ 就满足条件。但是可能会出现重复的情况，就是这两个点在x $x$ 的同一颗子树内，设连接这颗子树与x $x$ 的边的另一端点为y $y$ ，此时他们满足dis(u,y)+dis(v,y)+2dis(y,x)≤k $dis(u,y)+dis(v,y)+2dis(y,x)/leq k$ ，判一下减掉就好了。时间复杂度O(nlog2n) $O(nlog^2n)$ 另外，每次找的树根要尽量是的子树节点数的最大值最小，也就是找重心，否则如果出现一条链那就完了。

代码

#include <cstdio>#include <cstring>#include <algorithm>#define REP(i,_begin,_end) for(int i=(_begin);i!=(_end);++i)template<class T>T min(const T &a,const T &b){return a < b ? a : b;}template<class T>T max(const T &a,const T &b){return a > b ? a : b;}template<class T>bool chkmin(T &a,const T &b){return a > b ? a=b, 1 : 0;}template<class T>bool chkmax(T &a,const T &b){return a < b ? a=b, 1 : 0;}const int SN = 10000 + 50;const int Inf = 0x3f3f3f3f;int head[SN], nxt[SN<<1], to[SN<<1], wei[SN<<1], tot;int size[SN], dis[SN], d[SN], ans, rt, cnt, n, m, k, sum;bool vis[SN];void Init();void Add(int, int, int);void GetRt(int, int);void GetDis(int, int);int Calc(int, int);void Doit(int);int main(){ int x, y, z; while(scanf("%d%d",&n,&k)!=EOF && (n||k)){ Init(); REP(i, 1, n) scanf("%d%d%d",&x,&y,&z), Add(x, y, z); sum=n, cnt=Inf, GetRt(1,0), Doit(rt); printf("%d/n",ans); } return 0;}void Init(){ memset(head, 0, sizeof head), memset(nxt, 0, sizeof nxt); memset(vis, false, sizeof vis), tot=ans=0;}void Add(int u,int v,int w){ nxt[++tot]=head[u];head[u]=tot;to[tot]=v;wei[tot]=w; nxt[++tot]=head[v];head[v]=tot;to[tot]=u;wei[tot]=w;}void GetRt(int u,int fa){ int mx = 0; size[u] = 1; for(int i=head[u];i;i=nxt[i]) if(!vis[to[i]] && to[i]!=fa){ GetRt(to[i], u); size[u] += size[to[i]]; chkmax(mx,size[to[i]]); } if(chkmin(cnt,max(mx,sum-size[u]))) rt = u;}void GetDis(int u,int fa){ dis[dis[0]++] = d[u]; for(int i=head[u];i;i=nxt[i]) if(to[i]!=fa && !vis[to[i]]) d[to[i]] = d[u]+wei[i], GetDis(to[i],u);}int Calc(int u,int x){ d[u]=x, dis[0]=1; GetDis(u, -1); std :: sort(dis+1, dis+dis[0]); int res = 0; for(int l=1,r=dis[0]-1;l<r;) if(dis[l]+dis[r]<=k) res += r-l, ++l; else --r; return res;}void Doit(int u){ ans += Calc(u,0); vis[u] = true; for(int i=head[u];i;i=nxt[i]) if(!vis[to[i]]){ ans -= Calc(to[i],wei[i]); sum = size[to[i]]; cnt=Inf, GetRt(to[i], u); Doit(rt); }}

上一篇：4.2 结构类型——结构

下一篇：关于微信等app请求服务器,file_get_contents()函数和CURL用法