首先我们定义sum数组，sum[i]为[father[i],i)区间的和，对于一条信息，我们需要把闭区间转化成左闭右开区间，因为闭区间会割裂一些区间的联系，比如[1,2]和[3,3]是连通的区间，但是在程序中就会被判断成不连通。对于每个信息s,t,v，我们可以分两种情况，当s与t的祖先相同时，判断是否满足sum[t]-sum[s]=v,当祖先不同时，将他们的祖先合并，sum数组的维护体现在并查集的路径压缩中，具体的实现可参考代码
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxn 50000 int father[maxn],n,m,T; int sum[maxn],flag; void init(void) { for (int i=1;i<=n+5;i++) father[i]=i; for (int i=1;i<=n+5;i++) sum[i]=0; flag=0; } int getfather(int x) { int temp=father[x]; if (x!=father[x]) father[x]=getfather(father[x]); sum[x]+=sum[temp]; return father[x]; } int main() { scanf("%d",&T); while (T--) { scanf("%d%d",&n,&m); init(); for (int i=1;i<=m;i++) { int s,t,v; scanf("%d%d%d",&s,&t,&v); if (flag) continue; t++; int x=getfather(s); int y=getfather(t); if (x!=y) { father[y]=x; sum[y]=sum[s]+v-sum[t]; } else if (sum[t]-sum[s]!=v) flag=1; } if (flag) printf("false\n");else printf("true\n"); } return 0; }