(21725) 더치페이

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

단계별로 풀어보기

43단계(유니온 파인드 2) 7번째

 

 

 

x가 c원을 냈다면 x가 속한 그룹의 수를 d라고 할 때 x는 c-c/d원을 더 냈고 나머지 그룹원은 c/d원을 덜 냈다. 이것을 가중치로 생각하고 이전 문제처럼 풀 수도 있지만 굉장히 까다롭고, 정석은 DSU Tree를 쓰는 것이다.

DSU Tree는 일반적인 유니온 파인드와 비슷하지만 병합 과정에서 두 정점이 다른 그룹이라면 한쪽으로 합치는 대신 새로운 정점을 만들어 두 정점을 이 새로운 정점에 이어주는 방식이다.

 

나머지 그룹원이 c/d원을 덜 낸 것을 쿼리마다 갱신하면 O(N^2)로 시간초과가 날 것이다. 따라서 그룹의 루트 정점에 c/d를 기록해 두고 나중에 역추적으로 일괄 계산하면 된다. 만약 두 그룹이 합쳐진다면 각 그룹의 루트 정점에 기록된 금액은 남아있으면서 새로운 그룹에서 지출 쿼리가 생긴다면 두 그룹 다 적용해줘야 하는데, 이때 DSU Tree를 쓴다. 병합할 때 만들어진 새로운 루트 정점에 기록하면 이전 지출 기록을 보존하면서 새로운 그룹의 지출을 쉽게 관리할 수 있다. 또한 돈을 낸 사람은 -c원의 내야 할 금액(c원의 받아야 할 금액)이 있는 것이나 마찬가지이므로 정점이 개인적으로 가진 값을 따로 기록하여 거기 저장한다(이 문제는 1~N번 노드에만 로컬 값이 들어가므로 하나의 변수로 관리해도 상관없지만, 기본적으로 DSU Tree는 갱신을 위한 값과 로컬 값을 따로 저장하는 것이 정석이라고 함). 값을 갱신하는 부분 또한 DFS로 처리하는 것이 정석이지만 이 문제는 항상 번호가 큰 정점이 상위 노드이므로 역방향으로 for문을 돌려도 된다.

 

이렇게 계산하면 마지막에 모두의 필요 금액 cost(i)가 나오는데(양수라면 내야 하고 음수라면 받아야 함) cost(i)의 총합은 0이므로 1번을 기준으로 상대적인 cost(i)값을 재설정하고 2~N번 사람은 1번하고만 돈을 주고받으면 많아야 N-1번의 송금으로 모든 정산을 할 수 있다.

사실 이 문제의 채무 관계는 제로섬이고 두 사람이 송금을 주고받을 때마다 적어도 한 명의 채무기록은 없앨 수 있으므로 항상 N-1번 이하의 송금으로 모든 계산을 마칠 수 있다. 따라서 불가능해서 -1을 출력하는 경우는 없다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m, ans= 0;
  
  cin >> n >> m;
  
  vector<int> uf(n+1, -1); // 음수는 집합 크기(루트), 양수는 부모 정점
  vector<pair<long, long>> cost(n+1);
  vector child(n+1, vector<int> ());
  
  auto find= [&](auto self, int x) -> int {
    if(uf[x]<0)  return x;
    else  return uf[x]= self(self, uf[x]);
  };
  
  auto merge= [&](int x, int y){
    x= find(find, x);
    y= find(find, y);
    
    if(x==y)  return;
    
    int idx= uf.size();
    
    uf.push_back(uf[x]+uf[y]);
    cost.push_back({0, 0});
    child.push_back(vector<int> ());
    child[idx].push_back(x);
    child[idx].push_back(y);
    uf[x]= idx;
    uf[y]= idx;
  };
  
  while(m--){
    int t, x, y;
    
    cin >> t >> x >> y;
    
    if(t==1){
      merge(x, y);
    }else{
      cost[x].first-= y;
      
      x= find(find, x);
      cost[x].second+= y/-uf[x];
    }
  }
  
  for(int i=uf.size()-1;i>=1;i--){
    for(int elem:child[i]){
      cost[elem].second+= cost[i].second;
    }
  }
  
  int cnt= 0;
  cost[1].first+= cost[1].second;
  for(int i=2;i<=n;i++){
    cost[i].first+= cost[i].second;
    cnt+= cost[i].first!=0;
  }
  
  cout << cnt << "\n";
  for(int i=2;i<=n;i++){
    if(!cost[i].first)  continue;
    
    if(cost[i].first>0)  cout << i << " 1 " << cost[i].first << "\n";
    else  cout << "1 " << i << " " << -cost[i].first << "\n";
  }
  
  return 0;
}