题意:n个poeces,m个操作,! a b w 代表b比a重w,? a b 代表问询b比a重多少,如果可以推断,输出结果,否则UNKNOW。
思路:并查集+路径压缩
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int f[100010]; long long int r[100010]; int m,n; int a,b,c; char q[5]; int find(int x) { if(f[x]==x)return x; else { int ff=f[x]; f[x]=find(f[x]); r[x]+=r[ff]; return f[x]; } } int main() { while(scanf("%d%d",&n,&m)) { if(m==0&&n==0)return 0; for(int i=1;i<=n;i++) { f[i]=i; r[i]=0; } while(m--) { scanf("%s",q); if(q[0]=='!') { scanf("%d%d%d",&a,&b,&c); int aa=find(a); int bb=find(b); if(aa<bb) { f[bb]=aa; r[bb]=r[a]-r[b]+c; } else { f[aa]=bb; r[aa]=r[b]-r[a]-c; } } else { scanf("%d%d",&a,&b); if(find(a)==find(b))printf("%d\n",r[b]-r[a]); else printf("UNKNOWN\n"); } } } }