[BOJ 6497] 전력난

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

MST를 만드는 문제이다.

총 길이에서 MST를 만든 후 그 경로의 길이를 뺴주면 절약한 길이를 얻을 수 있다. 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <stdio.h>
 
#define INF 1e9
typedef long long ll;
using namespace std;
 
ll ans,t,n,m,parent[211111];
vector<pair<int,pair<int,int>>> v;
 
int find(int x){
    if(x == parent[x]){
        return x;
    }else{
        return parent[x] = find(parent[x]);
    }
}
void merge(int x,int y){
    x = find(x);
    y = find(y);
    parent[x] = y;
}
 
int main(){
    while(1){
        int n,m;
        cin >>m >>n;
        if(m == 0 && n == 0)return 0;
        
        ll tt=0;
        for(int i=0;i<n;i++){
            int a,b,c;
            cin >>a >>b>>c;
            tt += c;
            v.push_back({c,{a,b}});
            parent[i] = i;
        }
        sort(v.begin(),v.end());
        
        ans = 0;
        for(int i=0;i<n;i++){
            auto p = v[i];
            int x = find(p.second.first);
            int y = find(p.second.second);
            if(x!= y){
                ans += p.first;
                merge(p.second.first,p.second.second);
            }
        }
        cout << tt-ans <<endl;
        v.clear();
    }
    return 0;
}