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

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

1647번: 도시 분할 계획

백준 1647번 도시 분할 계획을 풀었다.

 

마을을 두 개로 분리하면서 집과 집 사이를 모두 연결하는 최소 비용을 구하는 문제다.

먼저 하나의 마을에 최소 스패닝 트리 문제를 적용한 후에 마지막으로 추가한 n-1번째 간선을 빼면 된다.

그러면 가장 큰 비용의 간선을 삭제함과 동시에 마을이 두 개로 나뉘어진다.

 

집의 최대 개수가 100,000개, 간선의 최대 개수는 1,000,000개다.

시간복잡도가 O(V^2)인 프림 알고리즘을 사용하면 O(10^10)가 나올테니 시간 초과가 뜰 것이다.

그래서 크루스칼 알고리즘과 힙을 사용한 프림 알고리즘을 사용했다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#pragma warning(disable:4996)
using namespace std;

#define INF	2147483647
typedef pair<pair<int, int>, int> edge;
typedef pair<int, int> node;
struct compare {
	bool operator()(edge a, edge b) {
		return a.second > b.second;
	}
};
struct compare_prim {
	bool operator()(node a, node b) {
		return a.second > b.second;
	}
};

int n, m;
priority_queue<edge, vector<edge>, compare> pq;
int parent[100001];
int MST_cost;
vector<int> temp_cost;

int findParent(int x) {
	if (parent[x] == x)
		return x;
	return parent[x] = findParent(parent[x]);
}

void unionParent(int x, int y) {
	int x_p = findParent(x);
	int y_p = findParent(y);
	if (x_p < y_p)
		parent[y_p] = parent[x_p];
	else
		parent[x_p] = parent[y_p];
}

bool isCycle(int x, int y) {
	int x_p = findParent(x);
	int y_p = findParent(y);
	if (x_p == y_p)
		return 1;
	else
		return 0;
}

void Kruskal() {
	for (int i = 1; i <= n; i++)
		parent[i] = i;

	while (!pq.empty()) {
		int start = pq.top().first.first;
		int end = pq.top().first.second;
		int cost = pq.top().second;
		pq.pop();

		if (isCycle(start, end) == 0) {
			unionParent(start, end);
			MST_cost += cost;
			temp_cost.push_back(cost);
		}
	}
}

int visited[100001];
vector<node> vertex[100001];
priority_queue<node, vector<node>, compare_prim> pq_prim;

void Prim_heap() {
	visited[1] = 1;
	for (int i = 0; i < vertex[1].size(); i++) {
		int next = vertex[1][i].first;
		int cost = vertex[1][i].second;
		pq_prim.push({ next,cost });
	}

	while (!pq_prim.empty()) {
		int cur = pq_prim.top().first;
		int cost = pq_prim.top().second;
		pq_prim.pop();

		if (visited[cur] == 0) {
			visited[cur] = 1;
			MST_cost += cost;
			temp_cost.push_back(cost);

			for (int i = 0; i < vertex[cur].size(); i++) {
				int next = vertex[cur][i].first;
				int next_cost = vertex[cur][i].second;
				if(visited[next]==0)
					pq_prim.push({ next,next_cost });
			}
		}
	}
	
	int max = 0;
	for (int i = 0; i < temp_cost.size(); i++)
		if (max < temp_cost[i])
			max = temp_cost[i];

	cout << MST_cost - max;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int start, end, cost;
		scanf("%d %d %d", &start, &end, &cost);
		vertex[start].push_back({ end,cost });
		vertex[end].push_back({ start,cost });
		pq.push({ {start,end},cost });
	}

	//Kruskal();
	//cout << MST_cost - temp_cost.back();
	Prim_heap();

	return 0;
}