4690: Never Wait for Weights
Time Limit: 15 Sec Memory Limit: 256 MBSubmit: 288 Solved: 129[][][]Description
在实验室中，Nathan Wada作为助手的职责是测定两个样品的重量差异。当样品的差异很小时，使用天平能比使用
弹簧秤得到更精确的结果，所以他只使用天平来测得一些样品的重量差。他偶尔会被询问一些样品的重量差，而他
能否回答这些问题取决于在回答相应问题时他已经得到的测量结果。由于他所在处理的测量数据是巨大的，所以他
希望你能写个程序帮他处理数据和回答问题。
Input
输入包含多组测试数据。每组数据第一行包含两个整数 N 和 M ，其中 N 表示样品的数量，
样品从 1 到 N 标号，满足 2≤N≤100000 。
接下来 M 行，每行包括一个测量结果或者询问，按时间顺序给出，满足 1≤M≤100000 。
一个测量结果被格式化为 ! a b w ，表示第 a 个样品比第 b 个样品轻 w 个单位重量
满足 a≠b,0≤w≤1000000 ，且任意的测试结果互不矛盾。
一个询问被格式化为 ? a b ，表示询问第 a 个样品比第 b 个样品轻多少个单位重量，满足 a≠b 。
输入以两个零作为结束。
Output
对于每个询问输出一行，如果能回答问题，则输出问题的答案，你可以认为答案的绝对值不超过 1000000
否则输出 UNKNOWN ，表示不能回答问题。
Sample Input
2 2 ! 1 2 1 ? 1 2 2 2 ! 1 2 1 ? 2 1 4 7 ! 1 2 100 ? 2 3 ! 2 3 100 ? 2 3 ? 1 3 ! 4 3 150 ? 4 1 0 0
Sample Output
1 -1 UNKNOWN 100 200 -50
HINT
Source
并查集。维护一个距离。乱搞一发就好了。
/************************************************************** Problem: 4690 User: ecnu161616 Language: C++ Result: Accepted Time:1064 ms Memory:4468 kb****************************************************************/ #includeusing namespace std; int fa[100100];long long dis[100100];int n, m; int find(int x) { if (fa[x] == x) return x; int root = find(fa[x]); dis[x] += dis[fa[x]]; fa[x] = root; return root;} void merge(int x, int y, long long d) { int fx = find(x); int fy = find(y); if (fx != fy) { fa[fx] = fy; dis[fx] = dis[y] - dis[x] + d; }} int main(){ #ifdef ULTMASTER freopen("a.in","r",stdin); #endif while (~scanf("%d%d", &n, &m)) { memset(dis, 0, sizeof(dis)); for (int i = 0; i <= n; ++i) fa[i] = i; while (m--) { char s[5], op; int a, b, w; scanf("%s", s); op = s[0]; if (op == '!') { scanf("%d%d%d", &a, &b, &w); merge(a, b, w); } else { scanf("%d%d", &a, &b); if (find(a) != find(b)) printf("UNKNOWN\n"); else printf("%d\n", dis[a] - dis[b]); } } } return 0;}