题意：给你长度为n的区间，m个询问：a，b，c，问这m个问题有多少个是错误的（矛盾）。
10 5 1 10 100 7 10 28 1 3 32 4 6 41 6 6 1
由6->6=1, 4->6=41 知4->5=40;
同理 由1->10=100,7->10=28 知1->7=72;
又由1->3=32,4-6=41 知1->7=73,与上面矛盾；
所以答案为1；
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define INF 1e8 #define eps 1e-8 #define LL long long #define maxn 100001 #define PI acos(-1.0) int father[2*maxn]; int sum[2*maxn]; int find(int x) { if(x==father[x]) return x; int t=father[x]; father[x]=find(father[x]); sum[x]+=sum[t]; return father[x]; } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { int a,b,c; for(int i=0;i<=n;i++) { father[i]=i; sum[i]=0; } int ans=0; while(m--) { scanf("%d%d%d",&a,&b,&c); int x,y; a--; x=find(a); y=find(b); if(x==y) { if(sum[a]-sum[b]!=c) ans++; } else if(x>y) { father[y]=x; sum[y]=sum[a]-sum[b]-c; } else { father[x]=y; sum[x]=sum[b]-sum[a]+c; } } printf("%d\n",ans); } return 0; } /* 10 5 1 10 100 7 10 28 1 3 32 4 6 41 6 6 1 */