bzoj1202 [ HNOI2005 ] --带权并查集+前缀和
2018-06-27 09:58:24来源:未知 阅读 ()
http://www.lydsy.com/JudgeOnline/problem.php?id=1202
记s[i]=a[1]+a[2]+...+a[i],即s[i]为前缀和。再令v[i]=s[f[i]]-s[i],其中f[i]为i的父亲。对于每个读入的x,y,k,将x,y视为结点,如果x与y的根结点相同,因为v[y]-v[x]=s[f[y]]-s[y]-s[f[x]]-s[x]且f[y]=f[x],所以v[y]-v[x]就是区间[x,y]的和,所以只需要判断v[y]-v[x]是否等于k就可以了。如果x与y的根结点不相同,合并两个节点并更新信息。
#include<cstdio> #include<cstring> using namespace std; int n,i,j,m,f[101],w,x,y,k,v[101]; bool flag; int find(int x){ if(x==f[x])return x; int tmp=f[x]; //记录原来的父亲 f[x]=find(f[x]); v[x]+=v[tmp]; //更新结点信息 return f[x]; } bool union1(int x,int y,int k){ int fx=find(x),fy=find(y); if(fx==fy){ if(v[y]-v[x]!=k)return 0; }else{ f[fy]=fx; v[fy]=k-v[y]+v[x]; //更新结点信息 } return 1; } int main() { scanf("%d",&w); while(w--){ memset(v,0,sizeof(v)); flag=0; scanf("%d%d",&n,&m); for(i=0;i<=n;i++)f[i]=i; for(i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&k); if(!flag&&!union1(x-1,y,k))flag=1; } if(flag)printf("false\n");else printf("true\n"); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- BZOJ1202: [HNOI2005]狡猾的商人(带权并查集) 2018-07-13
- 洛谷P1196 [NOI2002]银河英雄传说(带权并查集) 2018-07-06
- 洛谷P2439 [SDOI2005]阶梯教室设备利用(带权区间覆盖) 2018-07-06
- bzoj1202 [ HNOI2005 ] --带权并查集+前缀和 2018-06-17
- BZOJ2298: [HAOI2011]problem a(带权区间覆盖DP) 2018-06-17
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