[C++] 2350번 대운하

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

---

 

25/10/29

 

 

최소 스패닝 트리의 아이디어를 사용하는 문제이다.

---

 

문제 접근 방식:

 

 

주어지는 쿼리의 개수는 $K \leq 10\ 000$이고, 정점의 수 $N \leq 1\ 000$, 간선의 수 $M \leq 100\ 000$이다.

각 쿼리마다 모든 경로의 개수를 세는건 아무래도 좀 힘들 것 같다.(경로의 개수의 상한이 어느정도인지는 몰라도...)

결국 배가 지나가는 경로를 하나 잡으면 그 경로 상의 운하 폭의 "최솟값"이 지나가는 배의 폭을 결정한다.

즉, 우리는 배의 폭을 최대화하고 싶으므로, 어떤 경로를 잡던 간에 운하 폭의 "최솟값"이 "최대화"되기를 원한다.

따라서, 그리디적으로 생각해보면 그냥 최대 스패닝 트리(최소스패닝이 아니다)를 잡으면 된다.

이후 두 정점을 잡으면 그 트리를 따라가도록 경로를 잡으면 경로는 항상 유일하고, 가장 큰 운하폭을 따라가도록 경로를 만들 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 2350번 대운하
// MST
/*
접근 방법:
최대 스패닝 트리를 만들자.
이후 경로는 유일하다.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'

struct edge{
    int u, v, w;
    bool operator<(const edge& other) const {
        return w < other.w;
    }
};

int _find(int node, vector<int>& parent){
    if (parent[node] != node){
        parent[node] = _find(parent[node], parent);
    }
    return parent[node];
}

void _merge(int node1, int node2, vector<int>& parent, vector<int>& sz){
    int p1 = _find(node1, parent), p2 = _find(node2, parent);
    if (p1 == p2) return;
    if (sz[p1] > sz[p2]){
        parent[p2] = p1;
        sz[p1] += sz[p2];
    } else {
        parent[p1] = p2;
        sz[p2] += sz[p1];
    }
    return;
}

int bfs(int start, int end, const vector<vector<pair<int, int>>>& G){
    int N = G.size();
    vector<int> vis(N, 1001);
    queue<int> Q;
    Q.push(start);
    vis[start] = 1000;
    while (!Q.empty()){
        int now = Q.front(); Q.pop();
        if (now == end){
            return vis[end];
        }
        for (auto near : G[now]){
            int nxt = near.first; int w = near.second;
            if (vis[nxt] == 1001){
                vis[nxt] = min(vis[now], w);
                Q.push(nxt);
            }
        }
    }
    return 1000;
}

int main(void){
    fastio

    int N, M, K; cin >> N >> M >> K;

    vector<int> parent(N, 0);
    for (int i = 0; i < N; ++i){
        parent[i] = i;
    }
    vector<int> sz(N, 1);

    vector<edge> E;
    int i, j, w;
    for (int a = 0; a < M; ++a){
        cin >> i >> j >> w;
        i--; j--;
        E.push_back({i, j, w});
    }
    sort(E.begin(), E.end());

    vector<vector<pair<int, int>>> G(N);
    int cnt = 0;
    while (!E.empty() && (cnt < N-1)){
        edge e = E.back(); E.pop_back();
        if (_find(e.u, parent) != _find(e.v, parent)){
            _merge(e.u, e.v, parent, sz);
            G[e.u].push_back({e.v, e.w});
            G[e.v].push_back({e.u, e.w});
            cnt++;
        }
    }

    int u, v;
    while (K--){
        cin >> u >> v; u--; v--;
        cout << bfs(u, v, G) << endl;
    }
    return 0;
}