백준 13418번 학교 탐방하기 - C++(cpp) 풀이

---

 

1. 최소한의 길을 선택해서 모든 건물을 탐방해야 하므로, 스패닝 트리를 구하면 된다.
2. 오르막길에는 가중치 1, 내리막길에는 가중치 0을 준다.
3. 최악의 경로는 최대 스패닝 트리, 최적의 경로는 최소 스패닝 트리이다.

 

1. 최소한의 길을 선택해서 모든 건물을 탐방해야 하므로, 스패닝 트리를 구하면 된다.

 모든 건물을 방문하는 데 필요한 최소한의 길을 선택해야 한다. 즉, 최소 연결 부분 그래프 = 스패닝 트리를 구하면 된다. 모든 건물을 방문하려면 왔던 길을 되돌아가야 하기 때문에 문제가 생기지는 않을까 싶지만, 오르막길은 되돌아갈 때는 내리막길이 되고, 또 내리막길이 되돌아올 때 오르막길이 되는 것은 무효 처리하기 때문에 단순히 스패닝 트리를 구해도 문제가 되지 않는다.

 

2. 오르막길에는 가중치 1, 내리막길에는 가중치 0을 준다.

 오르막길에서만 피로도가 발생하므로 오르막길에만 가중치를 준다.

 

 

3. 최악의 경로는 최대 스패닝 트리, 최적의 경로는 최소 스패닝 트리이다.

 피로도가 최대가 되는 경우는 최대 스패닝 트리를 선택하는 경우이고, 이때의 피로도는 모든 간선의 가중치 합의 제곱이 된다. 반대로 피로도가 최소가 되는 경우는 최소 스패닝 트리를 선택하는 경우가 된다.

 

반응형

---

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef long long ll;
const int MAX = 1001;

int N, M, A, B, C, entrance;
int parent[MAX], sz[MAX];
piii roads[MAX*MAX];

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

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[a] = b;
    sz[b] += sz[a];
}

void init_union_find() {
    for (int i=0; i<MAX; i++) {
        parent[i] = i;
        sz[i] = 1;
    }
}

int mst() {
    ll ret = 1 - entrance;
    int cnt = 0;
    
    init_union_find();
    for (int i=0; i<M; i++) {
        if (cnt == N-1) break;
        
        piii road = roads[i];
        int s = road.second.first;
        int e = road.second.second;
        int c = road.first;
        if (find(s) == find(e)) continue;
        
        merge(s, e);
        if (c == 0) ret++;
        cnt++;
    }
    
    return ret * ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    cin >> A >> B >> entrance;
    for (int i=0; i<M; i++) {
        cin >> A >> B >> C;
        roads[i] = {C, {A, B}};
    }
    
    sort(roads, roads+M, greater<piii>());
    ll min_cost = mst();
    
    sort(roads, roads+M, less<piii>());
    ll max_cost = mst();

    cout << max_cost - min_cost;
    
    return 0;
}