백준21725 더치페이

작성일 | In

문제 링크

  • https://icpc.me/21725

사용 알고리즘

  • 유니온 파인드

시간복잡도

  • $O(N \log N)$

풀이

각 사람이 지출한 금액과 실제로 지출해야 하는 금액을 어떻게 잘 계산했다고 가정하고, 송금 과정을 구하는 방법부터 알아봅시다. 한 명이 “은행” 역할을 해서 돈을 적게 낸 사람은 은행에게 송금하고, 돈을 많이 낸 사람은 은행에게 돈을 받으면 $n-1$번의 송금만 필요합니다.

Union-Find를 이용해 그룹이 합칠 때마다 새로운 정점을 추가하면 그룹이 합쳐지는 과정을 트리로 나타낼 수 있습니다. 그룹이 돈을 지불할 때마다 그룹을 나타내는 정점에 지불한 돈을 더하면, 각 사람이 지불해야 하는 금액은 트리에서 자신의 조상 정점의 가중치를 모두 더한 것이 됩니다. 이는 DFS를 이용해 계산할 수 있습니다.

Union-Find 과정에서 $O(N \log N)$, DFS를 이용해 지불해야 하는 금액을 계산하는데 $O(N)$, 송금 과정을 복원하는데 $O(N)$이 걸리므로 전체 시간 복잡도는 $O(N \log N)$입니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using tl3 = tuple<ll,ll,ll>;

int P[101010], Node[101010], Size[101010];
int Find(int v){ return v == P[v] ? v : P[v] = Find(P[v]); }
void Merge(int u, int v){ Size[Find(v)] += Size[Find(u)]; P[Find(u)] = Find(v); }
int ID(int v){ return Node[Find(v)]; }
int SZ(int v){ return Size[Find(v)]; }

int N, Q, pv;
ll A[101010], C[202020], S[202020];
vector<int> G[202020];

void Union(int u, int v){
    pv++;
    G[pv].push_back(ID(u));
    G[pv].push_back(ID(v));
    Merge(u, v); Node[Find(v)] = pv;
}
void Use(int a, ll b){
    A[a] += b; C[ID(a)] += b/SZ(a);
}
void DFS(int v){
    S[v] += C[v];
    for(auto i : G[v]) S[i] += S[v], DFS(i);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    iota(P, P+101010, 0);
    iota(Node, Node+101010, 0);
    fill(Size, Size+101010, 1);
    cin >> N >> Q; pv = N;
    for(int q=1; q<=Q; q++){
        ll op, a, b; cin >> op >> a >> b;
        if(op == 1) Union(a, b);
        else Use(a, b);
    }
    DFS(ID(1));

    vector<tl3> Res;
    for(int i=2; i<=N; i++){
        ll val = S[i] - A[i];
        if(val > 0) Res.emplace_back(i, 1, val);
        if(val < 0) Res.emplace_back(1, i, -val);
    }
    cout << Res.size() << "\n";
    for(auto [s,e,x] : Res) cout << s << " " << e << " " << x << "\n";
}