1647 도시 분할 계획

MST + a 문제다.

마을을 두개로 나누어야 하는데 각각의 마을의 내부는 최소비용으로 연결되어있어야 한다.

MST를 구한 다음에 MST에 사용된 간선의 cost 중 가장 큰걸 빼면 된다.

#include <stdio.h>
#pragma warning(disable:4996)
typedef long long ll;
int n, m;
 
struct edge {
    int u, v, w;
    edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}
};
 
edge arr[1000001], temp[1000001];
 
void _sort(int l, int r) {
    if (l == r || r - 1 == l) return;
    int mid = (l + r) / 2;
    _sort(l, mid);
    _sort(mid, r);
 
    int cur = 0, l_cur = l, r_cur = mid;
    while (l_cur < mid && r_cur < r) {
        if (arr[l_cur].w < arr[r_cur].w) {
            temp[cur++] = arr[l_cur++];
        }
        else
            temp[cur++] = arr[r_cur++];
    }
    for (; l_cur < mid; l_cur++) temp[cur++] = arr[l_cur];
    for (; r_cur < r; r_cur++) temp[cur++] = arr[r_cur];
    for (int i = 0; i < r - l; i++) arr[l + i] = temp[i];
}
 
int d[100001];
 
int f(int x) {
    return x == d[x] ? x : d[x] = f(d[x]);
}
 
void u(int x, int y){
    x = f(x);
    y = f(y);
    if (x != y) d[y] = x;
}
ll max(ll a, ll b) { return a > b ? a : b; }
int main() {
    for (int i = 0; i < 100001; i++) d[i] = i;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        arr[i] = { a, b, c };
    }
    _sort(0, m);
    ll ans = 0, last = 0;
    for (int i = 0; i < m; i++) {
        if (f(arr[i].u) != f(arr[i].v)) {    
            u(arr[i].u, arr[i].v);
            ans += arr[i].w;
            last = max(last, arr[i].w);
        }
    }
    printf("%lld\n", ans - last);
 
    return 0;
}