[백준 1647] 도시 분할 계획

그냥 최소 신장 트리 구한 다음에 가장 큰 간선만 빼주면 된다.

 

MST 구했다는게 우선 모든 노드가 연결된 트리가 나왔다는 것이므로 

여기서 간선 하나만 빼주면 문제가 원하는대로 2개로 분할된 도시가 나오기 때문이다.

 

간선 가중치 합이 10억 이하이므로 int로만 돌려도 감당ㄱㄴ

 

---

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

#define SIZE 100001

using namespace std;

int N, M;
int parent[SIZE];

// 우선 전체 kruskal을 구하고
// 그 중 가장 큰 간선 값만 빼주면 됨
// 그게 이분할 되는거니까

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

void update_parent(int a, int b) {
	a = findParent(a);
	b = findParent(b);

	if (a != b) parent[b] = a;
}

bool isCycle(int a, int b) {
	a = findParent(a);
	b = findParent(b);

	return a == b;
}

// sorted vector가 들어옴
// 1.000.000.000 -> int로 충분함
int kruskal(vector<pair<int, pair<int, int>>> edges) {
	
	int ret = 0;
	int max = 0;
	for (int i = 0; i < edges.size(); i++) {
		int a = edges[i].second.first;
		int b = edges[i].second.second;
		int cost = edges[i].first;

		if (!isCycle(a, b)) {
			update_parent(a, b);
			ret += cost;
			if (cost > max) max = cost;
		}
	}
	return ret - max;
}

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

	cin >> N >> M;
	int A, B, cost;
	vector<pair<int, pair<int, int>>> edges;

	// parent 최신화
	for (int i = 1; i <= N; i++) parent[i] = i;

	for (int i = 0; i < M; i++) {
		cin >> A >> B >> cost;
		edges.push_back(make_pair(cost, make_pair(A, B)));
	}
	
	// key값으로 정렬
	sort(edges.begin(), edges.end());

	cout << kruskal(edges);

	return 0;
}