백준 1939번 중량제한 - C++ 풀이

---

 

1. 가중치 내림차순으로 간선을 정렬한다.
2. 두 공장이 이어질 때까지 간선을 하나씩 추가한다.

 

1. 가중치 내림차순으로 간선을 정렬한다.

 시작 공장에서 도착 공장으로 가는 경로에서 가중치가 가장 작은 간선이 한 번에 옮길 수 있는 중량의 최댓값을 결정한다. 

 

2. 두 공장이 이어질 때까지 간선을 하나씩 추가한다.

 따라서 시작 공장에서 도착 공장으로 가는 경로가 생성될 때까지 가중치가 큰 간선부터 차례로 추가해보면 된다. 가중치가 큰 순서로 추가했으므로, 최초로 경로가 만들어지는 순간에 추가한 간선이 경로 내에서 최소 가중치를 갖는 간선이 되므로 해당 간선의 가중치가 답이 된다.

 

반응형

---

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> pii;
typedef pair<int, pii> piii;

int N, M, S, E;
int parent[10001], sz[10001];
piii edges[100001];

int find(int n) {
    if (n == parent[n]) return n;
    return parent[n] = find(parent[n]);
}

void merge(int a, int b) {
    a = find(a); b = find(b);
    
    if (a == b) return;
    
    if (sz[a] < sz[b]) swap(a, b);
    parent[b] = a;
    sz[a] += sz[b];
}

int calcMaxWeight() {
    for (int i=0; i<10001; i++) {
        parent[i] = i;
        sz[i] = 1;
    }
    
    // 가중치가 큰 간선부터 두 공장이 이어질 때까지 선택한다
    sort(edges, edges+M, greater<piii>());
    
    for (auto edge: edges) {
        int c = edge.first;
        int a = edge.second.first;
        int b = edge.second.second;
        
        merge(a, b);
        
        if (find(S) == find(E)) return c;
    }
    
    return 1000000000;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    
    for (int i=0; i<M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        
        edges[i] = {c, {a, b}};
    }
    
    cin >> S >> E;
    
    cout << calcMaxWeight();

    return 0;
}