Algorithm/BOJ

전국시대 - 15809

jhg0406 2020. 3. 7. 05:08
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
//15809 - 전국시대
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int N, M;
 
struct DisjointSet
{
    vector<int> parent, rank, army;
 
    DisjointSet(int n) : parent(n), rank(n, 1), army(n)                                 
    {
        for(int i = 1; i<n; ++i)
            parent[i] = i;
    }
 
    void setArmy()
    {
        for(int i = 1; i<=N; ++i)
            cin >> army[i];
    }
 
    int find(int u)
    {
        if(u == parent[u]) return u;
        return parent[u] = find(parent[u]);
    }
 
    void merge(int u, int v)
    {
        u = find(u); v = find(v);
        if(u == v) return;
        if(rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        army[v] += army[u];
        if(rank[u] == rank[v]) ++rank[v];
    }
 
    void fight(int u, int v)
    {
        u = find(u); v = find(v);
        if(army[u] > army[v])
        {
            army[u] -= army[v];
            army[v] = 0;
            parent[v] = u;
        }
        else if(army[u] < army[v])
        {
            army[v] -= army[u];
            army[u] = 0;
            parent[u] = v;
        }
        else
            army[u] = army[v] = 0;
    }
};
 
int main()
{
    cin >> N >> M;
    DisjointSet sets(N+1);
    sets.setArmy();
    int flag, u, v;
    for(int i = 0; i<M; ++i)
    {
        cin >> flag >> u >> v;
        if(flag == 1)
            sets.merge(u, v);
        else
            sets.fight(u, v);
    }
    vector<int> bucket;
    for(int i = 1; i<=N; ++i)
        if(i == sets.find(i) && sets.army[i])
            bucket.push_back(sets.army[i]);
    sort(bucket.begin(), bucket.end());
    cout << bucket.size() << "\n";
    for(int i = 0; i<bucket.size(); ++i)
        cout << bucket[i] << " ";
}
 cs

 

 

 

 

 

 

https://www.acmicpc.net/problem/15809

 

15809번: 전국시대

첫 번째 줄에 국가의 수를 나타내는 N과 기록의 수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 두 번째 줄 부터 N개의 줄에 걸쳐 i번째 국가의 병력 Ai (1 ≤ i ≤ N)가 자연수로 주어진다. (1 ≤ Ai ≤ 10,000) 다음 M개의 줄에는 기록이 3개의 정수 O, P, Q로 주어진다. O가 1인 경우 P, Q가 서로 동맹을 맺었음을 의미하고, O가 2인 경우 P, Q가 서로 전쟁을 벌였음을 의미한다. 동맹끼리 다시 동맹을 맺거나 전쟁

www.acmicpc.net

 

 

 

 

 

 

전국 시대

union-find 문제입니다. 문제의 조건에 맞게 약간의 변형을 해주면 됩니다!