BZOJ1468: Tree
2018-06-17 21:25:57来源:未知 阅读 ()
Submit: 1736 Solved: 961
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
1 6 13
6 3 9
3 5 7
4 1 3
2 4 20
4 7 2
10
Sample Output
HINT
Source
LTC男人八题系列
HOME Back
点分治,真是个神奇的东西。
对于这个题而言,求出所有的距离,再利用双指针法统计答案
具体来说就是记录两个变量,当统计出一个点到其他点的距离时
如果到$l$+到$r$的距离是满足条件的,那么$l-r$中间的点就都满足条件
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN=1e6+10; const int INF=1e7+10; inline char nc() { static char buf[MAXN],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++; } inline int read() { char c=nc();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();} while(c>='0'&&c<='9'){x=x*10+c-'0',c=nc();} return x*f; } struct node { int u,v,w,nxt; }edge[MAXN]; int head[MAXN]; int num=1; inline void AddEdge(int x,int y,int z) { edge[num].u=x; edge[num].v=y; edge[num].w=z; edge[num].nxt=head[x]; head[x]=num++; } int K,F[MAXN],siz[MAXN],root,sum,vis[MAXN],tot[MAXN],cnt,deep[MAXN],ans=0; void GetRoot(int now,int fa) { siz[now]=1; for(int i=head[now];i!=-1;i=edge[i].nxt) { if(edge[i].v==fa||vis[edge[i].v]) continue; GetRoot(edge[i].v,now); siz[now]+=siz[edge[i].v]; F[now]=max(F[now],siz[edge[i].v]); } F[now]=max(F[now],sum-siz[now]); if(F[now]<F[root]) root=now; } void GetDeep(int now,int fa) { tot[++cnt]=deep[now]; for(int i=head[now];i!=-1;i=edge[i].nxt) { if(vis[edge[i].v]||edge[i].v==fa) continue; deep[edge[i].v]=deep[now]+edge[i].w; GetDeep(edge[i].v,now); } } int Calc(int now,int val)//now点满足条件的个数 { cnt=0;deep[now]=val;//一个小技巧 GetDeep(now,0); sort(tot+1,tot+cnt+1); int l=1,r=cnt,NowAns=0; while(l<r) { if(tot[l]+tot[r]<=K) NowAns+=r-l,l++; else r--; } return NowAns; } void Solve(int now) { vis[now]=1;//别忘了打标记 ans+=Calc(now,0); for(int i=head[now];i!=-1;i=edge[i].nxt) { if(vis[edge[i].v]) continue; ans-=Calc(edge[i].v,edge[i].w); sum=siz[edge[i].v]; root=0; GetRoot(edge[i].v,0); Solve(edge[i].v); } } int main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif memset(head,-1,sizeof(head)); int N=read(); for(int i=1;i<=N-1;i++) { int x=read(),y=read(),z=read(); AddEdge(x,y,z); AddEdge(y,x,z); } K=read(); F[0]=INF;sum=N; //这里有个技巧,把root设置为0,f[0]=INF,那么可以解决找重心时的边界问题 GetRoot(1,0); Solve(root); printf("%d",ans); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 设计一个多功能的MyTime类 代码参考 2020-03-29
- 设计MyTime类 代码参考 2020-03-29
- Maximum White Subtree 2020-03-26
- STL中_Rb_tree的探索 2020-02-20
- 二叉树(5)HuffmanTree 2020-02-19
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash