문제

문제 링크

문제 접근

  • 이 문제는 mst를 응용하면 풀 수 있을 것 이라 생각했다.
  • 최소값으로 도시를 두개 만든다면 최소값으로 mst를 만든 다음에 거기서 edge를 하나 빼면 된다.
  • 여기서 빠지는 edge는 유지비가 가장 큰 edge일 것임으로 n - 1개가 아닌 n - 2개 edge를 받으면 된다.

코드

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
#define pii pair<int, int>
#define pip pair<int, pii>
int ans, cnt, n, m, a, b, c, par[100001];

namespace fio {
    const int BSIZE = 524288;
    char buffer[BSIZE];
    char *p = buffer + BSIZE;
    inline char readChar() {
        if (p == buffer + BSIZE) {
            fread(buffer, 1, BSIZE, stdin);
            p = buffer;
        }
        return *p++;
    }
    int readInt() {
        char c = readChar();
        while (c < '0') c = readChar();
        int ret = 0;
        while (c >= '0')ret = ret * 10 + c - '0', c = readChar();
        return ret;
    }
}

int find(int i){
    if(par[i] == i)return i;
    return par[i] = find(par[i]);
}

int main(){
    n = fio::readInt(); m = fio::readInt();
    for(int i = 1; i <= n; i++)par[i] = i;
    priority_queue<pip> pq;
    for(int i = 0; i < m; i++){
        a = fio::readInt(); b = fio::readInt(); c = fio::readInt();
        pq.push(pip(-c, pii(a, b)));
    }
    while(!pq.empty() && cnt != n - 2){
        pip top = pq.top(); pq.pop();
        int tv = top.first, tx = top.second.first, ty = top.second.second;
        int px = find(tx), py = find(ty);
        if(px == py)continue;
        ans += -tv, cnt++;
        par[px] = py;
    }
    printf("%d", ans);
}

느낀점

  • 하나를 빼기만 하면 되는데 이 방법을 떠올리지 못했을 때는 복잡한 후처리를 해주려고 했다.
  • 그래도 스스로 떠올린 것에 만족한다.