|
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
#include <iostream>
#include <vector>
#include <cstring>
#define MAXX 100001
using namespace std;
int parent[MAXX];
int weightDiff[MAXX];
int unionSize[MAXX];
void init(int n)
{
for (int i = 1; i <= n; i++)
parent[i] = i;
}
int find(int a)
{
if (parent[a] == a)
return a;
else
{
int tmp = find(parent[a]);
weightDiff[a] += weightDiff[parent[a]]; //무게 누적합
return parent[a] = tmp;
}
}
//b가 a보다 k만큼 무겁다
void union_find(int a, int b, int k)
{
int pA = find(a);
int pB = find(b);
if (pA != pB) {
if (unionSize[pA] <= unionSize[pB]) {
//a를 b에 연결
parent[pA] = pB;
int diff = weightDiff[b] - weightDiff[a] - k;
//b에 a를 붙일 때는 parent[b]와 parent[a]의 차이 x
//x = diff[b] - k - diff[a]
weightDiff[pA] += diff;
unionSize[pB] += unionSize[pA];
unionSize[pA] = 1;
}
else {
//b에 a를 연결
//diff는 음수로 붙여준다.
parent[pB] = pA;
int diff = weightDiff[b] - weightDiff[a] - k;
//b에 a를 붙일 때는 parent[b]와 parent[a]의 차이 x
//x = diff[b] - k - diff[a]
weightDiff[pB] -= diff;
unionSize[pA] += unionSize[pB];
unionSize[pB] = 1;
}
}
}
bool isSame(int a, int b)
{
int parentA = find(a);
int parentB = find(b);
if (parentA == parentB)
return true;
return false;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
while (1)
{
int n, m;
cin >> n >> m;
if (n == 0 && m == 0)
break;
for (int i = 0; i <= n; i++) {
unionSize[i] = 1;
parent[i] = i;
weightDiff[i] = 0;
}
while (m--)
{
char c;
int a, b, w;
cin >> c >> a >> b;
if (c == '!')
{
//무게를 잰다.
cin >> w;
union_find(a, b, w);
}
else if (c == '?')
{
if (isSame(a, b))
{
cout << weightDiff[b]-weightDiff[a] << '\n';
}
else
{
cout << "UNKNOWN" << '\n';
}
}
}
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
'BOJ > C++' 카테고리의 다른 글
| [BOJ] 두 배열의 합 (0) | 2020.02.10 |
|---|---|
| [BOJ] 합이 0인 네 정수 (0) | 2020.02.10 |
| lca2 (0) | 2020.02.10 |
| 두 배열의 합 (0) | 2020.02.09 |
| 커피숍2 (0) | 2020.02.09 |