BOJ 1647번 도시 분할 계획

BOJ : https://www.acmicpc.net/problem/1647

 

마을을 최소의 가중치를 가지는 간선으로 연결한 후에

다시 2개의 집합으로 나누어야 한다

문제의 조건에서 마을에는 최소 1개의 집만 있으면 된다고 하였으므로

어떤 간선이든 잘라도 이 조건이 유지된다

그러므로 MST로 연결된 모든 간선 중에서 가장 큰 가중치를 갖는 간선을 삭제해주면 답이된다

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
#include <string>
using namespace std;
 
typedef pair<int, int> pii;
vector<pii> v[100005];
bool visit[100005];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    int N, M;
 
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ c,b });
        v[b].push_back({ c,a });
    }
 
    priority_queue<pii, vector<pii>, greater<pii> > q;
    visit[1] = true;
    for (int i = 0; i < v[1].size(); i++) q.push({ v[1][i].first, v[1][i].second });
    int cnt = N - 1;
    long long ret = 0;
    int maxw = 0;
    while (cnt) {
        int w = q.top().first;
        int n = q.top().second;
        q.pop();
        if (visit[n]) continue;
        visit[n] = true;
        ret += w;
        cnt--;
        maxw = max(maxw, w);
        for (int i = 0; i < v[n].size(); i++) if (!visit[v[n][i].second]) q.push({ v[n][i].first, v[n][i].second });
    }
    cout << ret - maxw;
 
    return 0;
}