[bzoj1202]狡猾的商人

记si表示前缀和,由于账本可以为负,所以si本身是没有限制的,然后每一条消息相当于让某两天的差值确定,连一条边,之后在每一次消息中,先判断两点是否连通,连通就直接判断,不连通就加上这条边即可,这个东西可以用带权的并查集来维护

[bzoj1202]狡猾的商人
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int t,n,m,x,y,z,f[105],v[105];
 4 int find(int k){
 5     if (k==f[k])return k;
 6     int t=find(f[k]);
 7     v[k]+=v[f[k]];
 8     return f[k]=t;
 9 }
10 bool add(int x,int y,int z){
11     int p=find(x),q=find(y);
12     if (p==q)return (v[y]-v[x]==z);
13     f[p]=q;
14     v[p]=v[y]-v[x]-z;
15     return 1;
16 }
17 int main(){
18     scanf("%d",&t);
19     while (t--){
20         scanf("%d%d",&n,&m);
21         bool flag=0;
22         memset(v,0,sizeof(v));
23         for(int i=0;i<=n;i++)f[i]=i;
24         for(int i=1;i<=m;i++){
25             scanf("%d%d%d",&x,&y,&z);
26             if (!add(x-1,y,z))flag=1;
27         }
28         if (flag)printf("false\n");
29         else printf("true\n");
30     }
31 }
View Code

 

上一篇:CSP-S 模拟105


下一篇:一次serialVersionUID引发的血案