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

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

1647번: 도시 분할 계획

 

접근방식

 

1. 집들을 연결하는 최소값임으로  MST(최소 스패닝 트리) 문제임을 인지

 

 

문제풀이 

 

1. 일반적인 스패닝 트리를 구현

2. 두마을로 분리를 하는 것은 연결된 스패닝 트리 간선중에서 가장 값이 큰 것을 제거해줌으로 구현

3. 저는 우선순위를 사용한 prim 알고리즘으로 구현했습니다.

 

아래는 정답 코드

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

int n, m, result = 0;
int cut_val = 0;
vector <pair<int, int>> vec[100001];
bool visited[100001] = { 0, };

void prim() {
	priority_queue <pair<int, int>> pq;
	for (int i = 0; i < vec[1].size(); i++) {
		int cost = vec[1][i].second;
		int pos = vec[1][i].first;
		pq.push(make_pair(-1 * cost, pos));
	}
	visited[1] = 1;

	while (!pq.empty()) {

		int cost = pq.top().first * -1;
		int pos = pq.top().second;
		pq.pop();

		if (visited[pos] == false) {
			visited[pos] = true;
			result += cost;
			
			cut_val = max(cut_val,cost);
			for (int i = 0; i < vec[pos].size(); i++) {
				int ncost = vec[pos][i].second;
				int npos = vec[pos][i].first;
				if (visited[npos] == false) {
					pq.push(make_pair(-1 * ncost, npos));
				}
			}


		}

	}

}

int main() {
	cin >> n >> m;
	int from, to, cost;
	for (int i = 0; i < m; i++) {
		cin >> from >> to >> cost;
		vec[from].push_back(make_pair(to, cost));
		vec[to].push_back(make_pair(from, cost));
	}

	prim();
	cout << result - cut_val << endl;


	return 0;
}