题解 P2294 【[HNOI2005]狡猾的商人】

2017-09-20 16:06:15


emm...我来加个并查集的新题解吧。。大概就是强行权值并查集一波,,然后在一个集内的话判一下是否合法就可以了

代码量极短

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m,f[1000],ff[1000],x,y,z,xx,yy;
bool flag;
int fa(int x){
    if (f[x]==x)return x;
    int k=f[x],kk=fa(f[x]);ff[x]+=ff[k];//加上父节点的权值然后连接到father
    f[x]=kk;return kk;//路径压缩
}
signed main(){
    ios::sync_with_stdio(false);
    cin>>t;while (t--){
        cin>>n>>m;flag=true;
        for (int i=0;i<=n;i++)f[i]=i,ff[i]=0;
        for (int i=1;i<=m;i++){
            cin>>x>>y>>z;x--;xx=fa(x);yy=fa(y);//考虑前缀和数组,x到y的和自然是a[y]-a[x-1],所以x要--
            if (xx!=yy){
                f[yy]=xx;ff[yy]=ff[x]+z-ff[y];//连边
            }else flag&=ff[x]+z==ff[y];//判断是否合法
        }if (flag)cout<<"true"<<endl;else cout<<"false"<<endl;
    }
}