1647 도시 분할 계획

BOJ::1647 도시 분할 계획

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

최소비용신장트리를 구한 뒤,

최소비용신장트리에서 가장 큰 가중치를 가지고 있는것만큼을 빼주면 된다.

#include <stdio.h>
#include <queue>
#include <vector>
#include <functional>
#define P pair<int,int>
using namespace std;
 
int n, m;
vector<P> edges[100001];
 
int prim() {
    int ans = 0;
    int M = 0;
    bool visited[100001] = { false, };
 
    priority_queue<P, vector<P>, greater<P>> pq;
    //1번에서 시작
    pq.push(P(0, 1));
    while (!pq.empty()) {
        P cur = pq.top();
        pq.pop();
 
        if (visited[cur.second]) continue;
        visited[cur.second] = true;
        
        ans += cur.first;
        if (cur.first > M) {
            M = cur.first;
        }
 
        for (int i = 0; i < edges[cur.second].size(); i++) {
            if (visited[edges[cur.second][i].second]) continue;
            pq.push(edges[cur.second][i]);
        }
    }
 
    ans -= M;
    return ans;
}
 
int main() {
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        edges[u].push_back(P(w, v));
        edges[v].push_back(P(w, u));
    }
 
    printf("%d\n", prim());
}