【题目链接】 

 

【题目大意】

　　给出一些区间和的数值，问是否存在矛盾

 

【题解】

　　用并查集维护前缀和之间的距离，每个节点保存到根节点的数值差，

　　如果保存的数值差的差与前缀和之差不相等，则矛盾

 

【代码】

#include 
     
      #include 
      
       using namespace std;const int N=110;int n,m,f[N],d[N];int sf(int x){    if(f[x]==x)return x;    int fx=f[x];    f[x]=sf(f[x]);    d[x]+=d[fx];    return f[x];}const int M=1010;int T;int st[M],en[M],cost[M];bool check(){    for(int i=1;i<=m;i++){        int x=st[i]-1,y=en[i];        int fx=sf(x),fy=sf(y);        if(fx!=fy){            f[fx]=fy;            d[fx]=cost[i]-d[x]+d[y];        }else{        	//printf("%d %d %d\n",d[y],d[x],cost[i]);            if(d[x]-d[y]!=cost[i])return 0;        }    }return 1;}int main(){    scanf("%d",&T);    while(T--){        scanf("%d%d",&n,&m);        for(int i=0;i<=n;i++)f[i]=i,d[i]=0;        for(int i=1;i<=m;i++)scanf("%d%d%d",&st[i],&en[i],&cost[i]);        if(check())puts("true");        else puts("false");    }return 0;}