[백준] 1647 도시 분할 계획

백준1647링크

마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.
각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다.

입력

N은 2이상 100,000이하인 정수
M은 1이상 1,000,000이하인 정수
길의 유지비 C (1 ≤ C ≤ 1,000)

출력

없애고 남은 길 유지비의 합의 최솟값

풀이

사이클 만들지 않는 최소 신장 트리를 만든 후 가장 큰 비용을 가지고 있는 길 하나를 제거하여 두 개의 분리된 마을로 분할

M(길의 수)가 크기가 크기 때문에 주의해서 데이터 타입 설정

#include <iostream>
#include<algorithm>
#include<vector>
#include<queue>

#define MAXN 100001

using namespace std;

vector<pair<int, int>> v;
vector<pair<int, int>> cost;

int parent[MAXN];

int findParent(int x) {

    if (parent[x] == x) return x;

    return parent[x] = findParent(parent[x]);

}

void Union(int x, int y) {

    x = findParent(x);
    y = findParent(y);

    parent[x] = y;

    findParent(x);
}



int main() {
    long long N, M;
    cin >> N >> M;

    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }

    int a, b, c;

    for (long long i = 0; i < M; i++) {

        cin >> a >> b >> c;

        v.push_back(make_pair(a, b));
        cost.push_back(make_pair(c, i));

    }
    
    //비용이 작은 순서대로 정렬
    sort(cost.begin(), cost.end());

    int maxCost = 0;

    long long result = 0;

    for (int i = 0; i < cost.size(); i++) {
		//사이클을 만들지 않는 경우
        if (findParent(v[cost[i].second].first) != findParent(v[cost[i].second].second)) { 

            Union(v[cost[i].second].first, v[cost[i].second].second);

            result += cost[i].first;

            maxCost = cost[i].first; //마을을 이루는 길 중에서 가장 큰 비용

        }

    }


    cout << result - maxCost;

    return 0;

}