2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest - Road Reform 링크
(2023.06.28 기준 Difficulty *1800)

문제

n개의 도시와 m개의 양방향 도로와 최대 속도 제한 k가 주어진다. 그리고 도로에는 속도 제한이 있다.
모든 도시 간 이동이 가능해지게끔 도로를 최대한 철거할 것이다. 이 때, 남은 도로 중 속도 제한 중 최대가 k와 정확하게 같아야 한다. 이를 위해 한 도로의 속도 제한을 1씩 조절이 가능하다. 이 조절 횟수를 최대한 줄였을 때의 조절 횟수 출력

알고리즘

간선의 비용을 알맞게 정하여 MST를 이루게 해야하며, 조절에 대한 부분은 그리디로 접근할 수 있다.

풀이

철거한 후 남은 도로들은 최대 k의 속도 제한을 가질 수 있다. k보다 낮을 순 있지만, k보다 높을 수는 없다. 그러므로 간선의 비용은 max(0, s - k)로 지정하여 크루스칼을 돌리면 된다. (s는 각 도로의 속도 제한)

여기서 끝일 수 있지만.. 아니다.
이 문제에서 원하는 것은 모든 도로의 속도 제한 중 최대는 k와 정확하게 일치해야 한다.
그러므로 만약 모든 도로의 속도 제한이 k보다 낮으면 결과는 0을 내뱉겠지만, 정답은 (k - 최대 속도 제한)이 될 것이다. k와 차이가 제일 적은 도로의 속도 제한을 k까지 올리는 것이 최적이니깐.

그러므로 간선의 비용을 정해줄 때, k와 도로의 속도 제한의 차이 중 제일 적은 값도 저장해두자.
그리고 크루스칼의 결과가 0이면, 모든 도로의 속도 제한이 k보다 낮았다는 뜻이 되므로 저장해두었던 차이를 출력해주면 된다. k와 제일 차이가 적은 도로를 사용하여 속도 제한의 최대를 k와 맞춰주는 것이 최적이니깐.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef tuple<int, int, int> tiii;

const int MAXN = 200000;

int pa[MAXN];
vector<tiii> edges;

int find(int u){
    if (pa[u] != u) pa[u] = find(pa[u]);
    return pa[u];
}

void merge(int u, int v){
    u = find(u); v = find(v);

    if (u < v) pa[v] = u;
    else pa[u] = v;
}

void solve(){
    int n, m, k; cin >> n >> m >> k;

    edges.clear();
    int relax = INT_MAX;
    for (int i = 0, x, y, s; i < m; i++){
        cin >> x >> y >> s;
        edges.push_back({max(0, s - k), --x, --y}); // 속도 제한은 최대 k
        relax = min(relax, abs(s - k)); // 모든 도로의 속도 제한이 k보다 낮을 때를 대비하여 저장하는 최소 차이
    }

    // MST
    iota(pa, pa + n, 0); sort(edges.begin(), edges.end());
    int ct = 0; ll result = 0;
    for (auto [w, u, v]: edges) if (find(u) != find(v)){
        merge(u, v);
        result += w;
        if (++ct == n - 1) break;
    }

    // MST의 결과가 0이면 사용된 모든 도로의 속도 제한이 k보다 낮다는 뜻이다.
    // 그러므로 k와 제일 차이가 적은 도로를 사용하여 속도 제한의 최대를 k와 맞춰주는 것이 최적이다.
    cout << (result ? result : relax) << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T; cin >> T;
    while (T--) solve();
}

• Python

import sys; input = sys.stdin.readline
from math import inf

def find(u):
    if pa[u] != u:
        pa[u] = find(pa[u])
    return pa[u]

def union(u, v):
    u = find(u); v = find(v)

    if u < v: pa[v] = u
    else: pa[u] = v

for _ in range(int(input())):
    n, m, k = map(int, input().split())

    edges = []
    relax = inf
    for _ in range(m):
        x, y, s = map(int, input().split())
        x -= 1; y -= 1
        edges.append((max(0, s - k), x, y)) # 속도 제한은 최대 k
        relax = min(relax, abs(s - k)) # 모든 도로의 속도 제한이 k보다 낮을 때를 대비하여 저장하는 최소 차이

    # MST
    pa = [i for i in range(n)]
    result = ct = 0
    for w, u, v in sorted(edges):
        if find(u) != find(v):
            union(u, v)
            result += w
            ct += 1
            if ct == n - 1:
                break

    # MST의 결과가 0이면 사용된 모든 도로의 속도 제한이 k보다 낮다는 뜻이다.
    # 그러므로 k와 제일 차이가 적은 도로를 사용하여 속도 제한의 최대를 k와 맞춰주는 것이 최적이다.
    print(result) if result else print(relax)