首页 > 代码库 > 【bzoj 1202】[HNOI2005] 狡猾的商人（图论--带权并查集+前缀和）
【bzoj 1202】[HNOI2005] 狡猾的商人（图论--带权并查集+前缀和）
题意：一个账本记录了N个月以来的收入情况，现在有一个侦探员不同时间偷看到M段时间内的总收入，问这个账本是否为假账。
解法：带权并查集+前缀和。
判断账本真假是通过之前可算到的答案与当前读入的值是否相同来完成。那么就是只有知道新读入的区间2端的（在相同区域内的！！）前缀和才可以判断，也就是这2个端点之前被纳入了相同的区域内才可以判断。于是，我们就可以想到并查集了。（( ′? ??`) 真的么......）
假设已知x~y月的总收入为d，那么s[y]-s[x-1]=d。一般前缀和是算上自己的，这里我理解s[i]为在 i 所在的区域内 i 之前的数的大小。接着，当x,y不在相同区域内时就将其合并，在时就判断。
P.S.网上似乎还有人用查分约束的方法做。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 7 const int N=105,M=1005; 8 int n,m; 9 int fa[N],f[N];10 bool flag;11 12 int ffind(int x)13 {14 if (fa[x]!=x)15 {16 int fx=fa[x];17 fa[x]=ffind(fx);18 f[x]+=f[fx];19 }20 return fa[x];21 }22 void ins(int x,int y,int d)23 {24 int fx=ffind(x),fy=ffind(y);25 if (fx!=fy)26 {27 fa[fx]=fy;//at ease28 f[fx]=f[y]+d-f[x];29 }30 else if (f[x]-f[y]!=d) flag=false;31 }32 int main()33 {34 int T;35 scanf("%d",&T);36 while (T--)37 {38 int x,y,d;39 scanf("%d%d",&n,&m);40 flag=true;41 for (int i=0;i<=n;i++) fa[i]=i,f[i]=0;42 for (int i=1;i<=m;i++)43 {44 scanf("%d%d%d",&x,&y,&d);//s[y]-s[x-1]=d45 if (flag) ins(x-1,y,d);46 }47 if (flag) printf("true\n");48 else printf("false\n");49 }50 return 0;51 }
我再附个图好了，自己真心理解了很久很久~(┬＿┬)
【bzoj 1202】[HNOI2005] 狡猾的商人（图论--带权并查集+前缀和）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。