[백준] 1647번 : 도시 분할 계획

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

1647번: 도시 분할 계획

최소비용 문제로 크루스칼 알고리즘을 사용하였다. 

이 문제에서 주어진 추가적인 조건은 두개의 마을로 분할해서 최소비용을 구하는 것이었다.

따라서, 일반적인 크루스칼 알고리즘을 통해 모든 정점을 이어서 구할 수 있는 최소 비용을 구한 후 선택된 간선들 중 가장 큰 가중치값을 갖는 간선치를 빼주었다. 해당 마을을 분할해주면 되기 때문이다.

 

전체 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M;

int getParent(int parent[], int x) {
	if (parent[x] == x) return x;
	else return parent[x] = getParent(parent, parent[x]);
}

void unionParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
}

int findParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a == b)return 1;
	else return 0;
}

class Edge {
public:
	int node[2];
	int distance;
	Edge(int a, int b, int distance) {
		this->node[0] = a;
		this->node[1] = b;
		this->distance = distance;
	}
	bool operator<(Edge& e) {
		return this->distance < e.distance;
	}
};

int main() {
	cin >> N >> M;
	int a, b, distance;
	vector<Edge> v;
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> distance;
		v.push_back(Edge(a, b, distance));
	}
	sort(v.begin(), v.end());
	int parent[100001];
	for (int i = 1; i <= N; i++) {
		parent[i] = i;
	}
	int sum = 0;
	int separate = 0;
	for (int i = 0; i < v.size(); i++) {
		if (!findParent(parent,v[i].node[0], v[i].node[1])) {
			unionParent(parent, v[i].node[0], v[i].node[1]);
			sum += v[i].distance;
			separate = max(separate, v[i].distance);
		}
	}
	cout << sum-separate << endl;
}