6497 전력난

MST + a 문제다.

현재 연결된 간선을 주고 모든 도시가 연결되어 있다는 조건을 지킨다는 전제 하에 얼마나 더 절약할 수 있는지를 물어본다.

모든 간선의 cost를 더한 후 MST를 구하고 sum_of_cost - cost(MST)를 구하면 된다.

#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[200001], temp[200001];
 
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[200001];
 
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() {
    while (1) {
        scanf("%d%d", &n, &m);
        if (n == 0 && m == 0) break;
        for (int i = 0; i < 200001; i++) d[i] = i;
        ll ans = 0, sum = 0;
        for (int i = 0; i < m; i++) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            arr[i] = { a, b, c };
            sum += c;
        }
        _sort(0, m);
        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;
            }
        }
        printf("%lld\n", sum - ans);
    }
    return 0;
}