Bnu33684Never Wait for Weights
注意：种类并查集要取模，注意有减法时，+MOD
#pragma comment(linker, "/STACK:1024000000,1024000000") #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define FE(i, a, b) for(int i = (a); i <= (b); ++i) #define FD(i, b, a) for(int i = (b); i >= (a); --i) #define REP(i, N) for(int i = 0; i < (N); ++i) #define CLR(a, v) memset(a, v, sizeof(a)) #define PB push_back #define MP make_pair #define RI(n) scanf("%d", &n) #define RIII(a, b, c) scanf("%d%d%d",&a, &b, &c) typedef long long LL; const double eps = 1e-10; const int maxn = 1000010; int fa[maxn], dis[maxn]; int findset(int x) { if (x != fa[x]) { int fax = fa[x]; fa[x] = findset(fa[x]); dis[x] += dis[fax]; } return fa[x]; } void Merge(int x, int y, int z) { int fax = findset(x); int fay = findset(y); if (fax == fay) return ; fa[fax] = fay; dis[fax] = dis[y] - dis[x] - z; } int main() { int n, m; char op; int x, y, z; while (cin >> n >> m && n + m) { for (int i = 0; i <= n; i++) fa[i] = i, dis[i] = 0; while (m--) { scanf(" %c%d%d", &op, &x, &y); if (op == '!') { scanf("%d", &z); Merge(x, y, z); } else { int fax = findset(x); int fay = findset(y); if (fax != fay) puts("UNKNOWN"); else printf("%d\n", dis[y] - dis[x]); } } } }