[1647번] 도시 분할 계획

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 최소 스패닝 트리(MST) :: http://www.crocus.co.kr/733

2. 유니온 파인드(Union Find) :: http://www.crocus.co.kr/683

최소 스패닝 트리의 크루스칼 알고리즘을 이용하여 생성하되 이때, 정답은 모든 마을을 최소 스패닝 트리로 연결하고

마지막으로 연결한 간선의 길이를 빼주면 정답이 된다.

이렇게 한다면 2개의 마을이 생기고 최소 거리로 모든 마을을 이을 수 있다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
typedef struct kruskal {
    int from;
    int to;
    int val;
}KS;
 
vector<KS> edge;
 
int parent[100002];
int res;
 
bool comp(KS d1, KS d2)
{
    return d1.val < d2.val;
}
 
// 유니온 파인드의 파인드 방식
int find(int num)
{
    if (num == parent[num])
        return num;
 
    return parent[num] = find(parent[num]);
}
int main()
{
    int V, E;
 
    scanf("%d %d", &V, &E);
 
    for (int i = 1; i <= V; i++)
        parent[i] = i;
 
    // 그래프 형성
    for (int i = 0; i < E; i++)
    {
        KS ks;
        scanf("%d %d %d", &ks.from, &ks.to, &ks.val);
        edge.push_back(ks);
    }
 
    // 크루스칼 알고리즘에 의해 간선을 오름차순 정렬
    sort(edge.begin(), edge.end(), comp);
 
    // 유니온 파인드의 유니온 방식
    int last;
    for (int i = 0; i < E; i++)
    {
        int nv = find(edge[i].from);
        int nw = find(edge[i].to);
 
        if (nv == nw)
            continue;
 
        parent[nv] = nw;
 
        res += edge[i].val;
        last = edge[i].val;
    }
 
    printf("%d", res - last);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>