[백준 1647번] 도시 분할 계획 (C++)

문제링크 : https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

struct p
{
    int u, v, weight;
    bool operator<(p const &e) //가중치가 작은 것부터
    {
        return weight < e.weight;
    }
};

int N, M, result;
int parent[100001];
vector<p>v;

int find_root(int x) //부모찾기
{
    if(x == parent[x]) return x;
    return parent[x] = find_root(parent[x]);
}

bool check(int a, int b) //이어졌는가?
{
    a=find_root(a);
    b=find_root(b);
    if(a==b) return 1;
    return 0;
}

void Union(int a, int b) //병합
{
    a=find_root(a);
    b=find_root(b);
    parent[b]=a;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;
    for(int i=0; i<M; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v.push_back({a, b, c});
    }

    sort(v.begin(), v.end());

    for(int i=1; i<=N; i++) //부모 초기화
    {
        parent[i] = i;
    }

    int maxV = 0;
    for(int i=0; i<M; i++)
    {
        if (!check(v[i].u, v[i].v)) //부모가 다르면 (이어져있지 않다면)
        {
            maxV = max(maxV, v[i].weight); //가장 유지비가 높은 가중치 저장 (분리예정)
            Union(v[i].u, v[i].v); //간선 이어주기
            result += v[i].weight; //가중치 합산
        }
    }

    cout << result - maxV; 

    return 0;
}

백준 1197번과 유사하게 크루스컬이나 프림 알고리즘으로 풀 수 있는 최소 스패닝 트리 (MST) 문제이다.

참고 : https://blob-thinking.tistory.com/248

[백준 1197번] 최소 스패닝 트리 (C++)

 

해당 문제와 다른 점은 만든 최소 스패닝 트리를 2개로 분리해야 하는 점이다.

2개로 분리할때 기존에 이어졌던 길은 필요가 없고, 유지비의 합을 최소로 하고자한다.

따라서 기존 최소 스패닝 트리에서 가장 가중치가 큰 간선을 제거하여 마을을 2개로 분리시켜 주면된다.

 

이를 위해 가장 유지비가 높은 가중치를 따로 저장하고, 출력할때 기존 MST의 가중치에서 해당 가중치를 빼서 출력을 해주었다.