Hihocoder #1515 : 分数调查

#1515 : 分数调查

http://hihocoder.com/problemset/problem/1515

分析

带权并查集。

如果把每个人抽象成一个点，之间的关系抽象成边。那么如果询问的两个人之间存在关系，说明，他们在图上上是联通的。所以并查集维护一下连通性。 对于分数之间的关系，用到带权并查集。

每个点里存一个val表示当前点的分数-根节点的分数。

查询： xy不连通，输出-1， 否则val[x]=fen[x]-fen[u],val[y]=fen[y]-fen[u]，输出fen[x]-fen[y]=val[x]-val[y]

合并： x的根节点为u，y的根节点为v，fa[u]=v; 更新后的val[u]=fen[u]-fen[v]，

由 val[x]=fen[x]-fen[u]，得 fen[u]=fen[x]-val[x]

由 val[y]=fen[y]-fen[v]，得 fen[v]=fen[y]-val[y]

所以 fen[u]-fen[v] = fen[x] - fen[y] + val[y] - val[x] = S + val[y] - val[x]

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = ;

int fa[N],val[N];

int find(int x) {

    if (x == fa[x]) return x;

    int tmp = find(fa[x]);

    val[x] += val[fa[x]];

    fa[x] = tmp;

    return fa[x];

}

int main() {

    int n = read(), m = read(), k = read();

    for (int i=; i<=n; ++i)

        fa[i] = i, val[i] = ;

    for (int i=; i<=m; ++i) {

        int x = read(),y = read(),S = read();

        int u = find(x),v = find(y);

        if (u != v) {

            fa[u] = v;

            val[u] = val[y] - val[x] + S;

        }

    }

    while (k--) {

        int x = read(),y = read();

        if (find(x) != find(y)) puts("-1");

        else {

            printf("%d\n",val[x]-val[y]);

        }

    }

    return ;

}