http://acm.hdu.edu.cn/showproblem.php?pid=3038
题意:数组第a个元素到第b个元素之间的和为sum;
求有几句话是假的,如果与前面的话有冲突就为假;
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<math.h> #define N 201000 #define INF 0xfffffff using namespace std; int f[N],vis[N],r[N]; int Find(int x) { int k = f[x]; if(x != f[x]) { f[x] = Find(f[x]); r[x] += r[k]; } return f[x]; } int main() { int px, py, ans, i, n, m, x, y, sum; while(scanf("%d%d", &n, &m)!=EOF) { for(i=0;i<=n;i++) f[i]=i,r[i]=0; ans = 0; while(m--) { scanf("%d%d%d", &x, &y, &sum); x --; px = Find(x); py = Find(y); if(px != py) { f[px] = py; r[px] = r[y] -r[x] - sum; } else if(r[y]-r[x] != sum) ans++; } printf("%d\n",ans); } return 0; }
How Many Answers Are Wrong----hdu3038
原文:http://www.cnblogs.com/zhengguiping--9876/p/4677617.html