题目链接:https://hihocoder.com/problemset/problem/1515
时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi的学校总共有N名学生，编号1-N。学校刚刚进行了一场全校的古诗文水平测验。
学校没有公布测验的成绩，所以小Hi只能得到一些小道消息，例如X号同学的分数比Y号同学的分数高S分。
小Hi想知道利用这些消息，能不能判断出某两位同学之间的分数高低？

输入

第一行包含三个整数N, M和Q。N表示学生总数，M表示小Hi知道消息的总数，Q表示小Hi想询问的数量。
以下M行每行三个整数，X, Y和S。表示X号同学的分数比Y号同学的分数高S分。
以下Q行每行两个整数，X和Y。表示小Hi想知道X号同学的分数比Y号同学的分数高几分。  

对于50%的数据，1 <= N, M, Q <= 1000
对于100%的数据，1 <= N, M, Q<= 100000 1 <= X, Y <= N -1000 <= S <= 1000
数据保证没有矛盾。

输出

对于每个询问，如果不能判断出X比Y高几分输出-1。否则输出X比Y高的分数。

样例输入

10 5 3
1 2 10
2 3 10
4 5 -10
5 6 -10
2 5 10
1 10
1 5
3 5

样例输出

-1
20
0

解题思路

带权并查集裸题，注意之所以可以在递归回溯过程中采用dis+=，是因为并查集的路径压缩，不会导致某个点到根结点的权值重复叠加。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int f[MAXN], dis[MAXN];
int getf(int v) {
    if (f[v] != v) {
        int tmp = f[v];
        f[v] = getf(f[v]);
        dis[v] += dis[tmp];
        return f[v];
    }
    return v;
}
void merge(int u, int v, int s) {
    int t1 = getf(u);
    int t2 = getf(v);
    if (t1 != t2) {
        f[t2] = t1;
        dis[t2] = dis[u] + s - dis[v];
    }
}
int main() {
    int n, m, q, x, y, s;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++) {
        f[i] = i;
        dis[i] = 0;
    }
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d",  &x, &y, &s);
        merge(x, y, s);
    }
    while (q--) {
        scanf("%d%d", &x, &y);
        if (getf(x) != getf(y))
            printf("-1\n");
        else printf("%d\n", dis[y] - dis[x]);
    }
    return 0;
}