Main » 2013 September 28 » [NOIP2012模拟赛No.6]狡猾的商人
11:09 AM [NOIP2012模拟赛No.6]狡猾的商人 |
并查集#include<cstdio> #define N 1001 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; int f[N],g[N]; int getf(int x) {if (f[x]==x) return x;int tf=getf(f[x]);g[x]+=g[f[x]];return (f[x]=tf);} int Main() { int i,F=1,n,m,x,y,z; scanf("%d%d",&n,&m); FOR(i,0,n) {f[i]=i;g[i]=0;} FOR(i,1,m) { scanf("%d%d%d",&x,&y,&z); int u=getf(x-1),v=getf(y); if (u!=v) {f[u]=v;g[u]=g[y]-z-g[x-1];} else if (g[y]-g[x-1]!=z) {F=0;break;} } F?printf("true\n"):printf("false\n"); } int main(){int w,i;scanf("%d",&w);FOR(i,1,w) Main();} |
|
|
| Total comments: 0 | |