백준 1647 도시 분할 계획 (c++) : 피너클

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

1647번: 도시 분할 계획

최소 스패닝 트리 문제다.

스패닝 트리를 돌린 뒤 마지막에 더한 cost를 빼줄것이다.

int n, m;
int parent[100001];
vector<pair<int, pair<int, int>>> edges;

 

사용할 변수다.

parent는 유니온 파인드에 사용할것이고 edges는 입력받을때와 스패닝 트리에서 사용할것이다.

int find(int num) {
	if (parent[num] == num) return num;
	else return parent[num] = find(parent[num]);
}

find함수다. num의 조상을 찾아 반환한다.

void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	parent[u] = v;
}

merge함수다. u와 v를 합친다.

for (int i = 0; i <= n; i++) parent[i] = i;
for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    edges.push_back({ c ,{a, b} });
}
cout << solve() << endl;

main함수다.

parent를 초기화한뒤 값을 입력받고 edegs에 저장한다. 그후 solve를 출력하면 된다.

int solve() {
	sort(edges.begin(), edges.end());
	int ans = 0, last = 0;

solve함수다.

edegs를 유지비를 기준으로 정렬한다.

ans는 총 유지비의 합이고 last는 마지막에 ans에 더한 유지비다.

	for (int i = 0; i < m; i++) {
		int cost = edges[i].first;
		int u = edges[i].second.first, v = edges[i].second.second;
		if (find(u) == find(v)) continue;
		ans += cost;
		merge(u, v);
		last = cost;
	}

이제 m만큼 반복문을 돌린다. m은 edges의 크기와 같다.

cost와 u, v를 꺼내준뒤 만약 u와 v의 조상이 같다면 뒤의 코드를 무시하고

아니면 ans에 cost를 더한뒤 u와 v를 합쳐준다.

그후 last를 이번 cost로 업데이트해준다.

현재 edges는 cost를 기준으로 정렬되어 있으니 마지막에 더해진 cost가 가장 큰 유지비다.

	return ans - last;
}

마지막으로 ans에서 last를 뺀 값을 반환한다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, m;
int parent[100001];
vector<pair<int, pair<int, int>>> edges;

int find(int num) {
	if (parent[num] == num) return num;
	else return parent[num] = find(parent[num]);
}

void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	parent[u] = v;
}

int solve() {
	sort(edges.begin(), edges.end());
	int ans = 0, last = 0;
	for (int i = 0; i < m; i++) {
		int cost = edges[i].first;
		int u = edges[i].second.first, v = edges[i].second.second;
		if (find(u) == find(v)) continue;
		ans += cost;
		merge(u, v);
		last = cost;
	}
	return ans - last;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;

	for (int i = 0; i <= n; i++) parent[i] = i;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edges.push_back({ c ,{a, b} });
	}
	cout << solve() << endl;
}

전체코드다.