[CodeForces - 362D] Fools and Foolproof Roads

난이도: 2100

 

태그

• Greedy
• Graph Theory
  • Connected Component
• Disjoint Set Union
• Priority Queue

 

풀이

1. 다른 Region에 있는 도시는 몇 번 연결해야 하는가?

다른 Region에 있는 도시를 하나 연결할 때마다 연결 요소의 개수가 1씩 줄어들게 됩니다.

그러므로, 입력된 그래프의 연결 요소를 \( c \)라고 할 때, \( q-c \)번 연결해야겠죠.

 

2. 답이 No인 경우는?

[1]에 따르면, 연결 횟수인 \( p \)는 \( 0 \le p \le q-c \)여야 합니다.

이를 만족하지 못한다면, 답은 No가 되겠죠.

 

No가 나오는 케이스가 하나 더 있는데, \( m = 0, p \neq 0, q = n \)입니다.

미리 연결된 도시는 없고, 이 상태에서 도시는 연결해야 하는데 Region 개수를 줄이면 안 되는 경우죠.

// 무슨 도시를 선택하든, 첫 연결은 Region의 개수를 줄이게 됩니다.

// 그런데, Region의 개수가 줄어들면 안 되므로 불가능하죠.

 

3. 다른 Region 간의 연결과 같은 Region 간의 연결 중 무엇을 먼저 해야 할까?

Exchange Argument를 생각해봅시다.

다른 Region에 속한 두 도시 \( a, b \)와 같은 Region에 속한 두 도시 \( c, d \)를 두면, 아래와 같은 상황을 생각해볼 수 있습니다.

// 편의상, \( a \)가 속한 Region을 \( A \)라고 표현하겠습니다.

// 이는 \( b, c, d \)에 대해서도 마찬가지입니다.

• \( A \neq C \), \( B \neq C \): 3개의 Region이 모두 다른 경우입니다.
  이 때에는 자명히 두 연결 간의 순서가 상관이 없겠죠.
• \( A = C \): 두 간선이 공유하는 Region이 있는 경우입니다.
  // \( B = C \) 역시 이 케이스에 해당됩니다.
  이 때에는 \( A, B \)를 먼저 연결한 뒤 \( A, A \)를 연결해야 합니다.
  // 앞의 경우는, \( (|A|+|B|+1) + (1000) \)의 비용이 드는 반면,
  // 뒤의 경우는, \( (1000) + (|A|+1000+|B|+1) \)의 비용이 들기 때문입니다.

 

그러니, 항상 다른 Region 간의 연결을 우선하면 됩니다.

다르게 말하자면, 다른 Region 간의 연결부터 다 한 뒤 남은 건 같은 Region 간의 연결로 때우면 된다는 의미죠.

 

4. 다른 Region에 있는 도시 간의 연결 순서는 어떻게 되어야 할까?

유명한 그리디 문제입니다.

현재까지 사용된 간선 합이 가장 적은 두 Region을 선택한 뒤 합쳐주면 되죠.

 

/// [TODO] 여기에 증명 적기

 

5. 코드

int par[100020]; ll siz[100020];
int fnd(int v){ return par[v] = (par[v]==v ? v : fnd(par[v])); }
void uni(int v, int w, ll x){
    int pv = fnd(v), pw = fnd(w);
    if (pv == pw){ siz[pv] += x; }
    else{ par[pv] = pw; siz[pw] += siz[pv] + x; }
    siz[pw] = min<ll>(siz[pw], 1e9);
}
 
void Main(){
    int n, m, k, t; cin >> n >> m >> k >> t;
    for (int i = 1; i <= n; i++){ par[i] = i; }
    if (m == 0){
        if (k > 0 && n == t){ cout << "NO"; return; }
    }
    while (m--){
        int v, w; ll x; cin >> v >> w >> x; uni(v, w, x);
    }
    priority_stack<pl2> pq;
    for (int i = 1; i <= n; i++){
        if (par[i] != i){ continue; }
        pq.push({siz[i], i});
    }
    int cnt = pq.size();
    if (t > cnt || cnt-k > t){ cout << "NO"; return; }
    cout << "YES" << endl;
    while (cnt > t){
        pl2 p1 = pq.top(); pq.pop();
        pl2 p2 = pq.top(); pq.pop();
        ll a = p1.fr, b = p2.fr;
        int v = p1.sc, w = p2.sc;
        cout << v << ' ' << w << endl;
        uni(v, w, a+b+1); pq.push({siz[w], w});
        cnt -= 1; k -= 1;
    }
    int v = 0, w = 0;
    for (int i = 1; i <= n; i++){
        if (par[i] != i){ v = i; w = fnd(i); }
    }
    while (k--){ cout << v << ' ' << w << endl; }
}