带权并查集

HihoCoder

小Hi的学校总共有N名学生，编号1-N。学校刚刚进行了一场全校的古诗文水平测验。

学校没有公布测验的成绩，所以小Hi只能得到一些小道消息，例如X号同学的分数比Y号同学的分数高S分。

小Hi想知道利用这些消息，能不能判断出某两位同学之间的分数高低？

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

Input

第一行包含三个整数N, M和Q。N表示学生总数，M表示小Hi知道消息的总数，Q表示小Hi想询问的数量。

以下M行每行三个整数，X, Y和S。表示X号同学的分数比Y号同学的分数高S分。

以下Q行每行两个整数，X和Y。表示小Hi想知道X号同学的分数比Y号同学的分数高几分。

Output

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

sample Input

10 5 3  
1 2 10  
2 3 10  
4 5 -10  
5 6 -10  
2 5 10  
1 10  
1 5  
3 5
Copy
1
2
3
4
5
6
7
8
9

Sample Output

-1

20

0

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;

int n, m, q;
int pre[N];
int val[N];

void init()
{
    for(int i = 0; i <= n; ++i)
    {
        pre[i] = i;
        val[i] = 0;
    }
}

int found(int x)
{
    if(x == pre[x])
        return x;

    int tem = pre[x];
    pre[x] = found(pre[x]);
    val[x] = val[x] + val[ tem ];
    return pre[x];
}

void unite(int x, int y, int s)
{
    int xx = found(x);
    int yy = found(y);
    if(xx != yy)
        pre[yy] = xx;
    val[yy] = s + val[x] - val[y];///类似向量
}

int main()
{
    while(~scanf("%d%d%d", &n, &m, &q))
    {
        init();
        int x, y, s;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d%d", &x, &y, &s);
            unite(x, y, s);
        }
        while(q--)
        {
            scanf("%d%d", &x, &y);
            int xx = found(x);
            int yy = found(y);
            if(xx != yy)
                cout << "-1" << '\n';
            else
                cout << val[y] - val[x] << '\n';///x离其公共祖先近,val[x]更小
        }
    }
    return 0;
}
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

关于Found递归函数的探索

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;

int n, m, q;
int pre[N];
int val[N];

void init()
{
    for(int i = 0; i <= n; ++i)
    {
        pre[i] = i + 1;
        val[i] = 1;
    }
    pre[n] = n;
    val[n] = 0;
}

int found(int x)
{
    cout << "x : " << x << '\n';
    if(x == pre[x])
        return x;

    int tem = pre[x];
    cout << x << "'s initial pre is " << tem << '\n';
    pre[x] = found(pre[x]);///程序返回后向下运行

    cout << x << "'s final pre is " << pre[x] << '\n';
    cout << "initial val[" << x << "] : " << val[x] << '\n';
    cout << "now val[" << tem << "] : " << val[tem] << '\n';

    val[x] = val[x] + val[ tem ];
    cout << "val[" << x << "] : " << val[x] << '\n';
    return pre[x];
}

//int found(int x)
//{
//    if(x == pre[x])
//        return x;
//
//    int tem = pre[x];
//
//    pre[x] = found(pre[x]);///向里递归，压缩每个节点的路径
//
//    val[x] = val[x] + val[ tem ];///向外return，更新每个节点的val
//    return pre[x];
//}

int main()
{
    n = 5;
    init();
    for(int i = 0; i <= 5; ++i)
        cout << i << ' ' << pre[i] << ' ' << val[i] << '\n';
    cout << found(0) << '\n';
}
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

妙不可言…

戴荃并查集：我要,这铁棒有何用？我要，这变化又如何？