[백준] 10021번 - Watering the Fields (C++) 문제 및 풀이

문제) 백준 - 최소 스패닝 트리(Minimum Spanning Tree) - Watering the Fields

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

10021번: Watering the Fields

 

네트워크를 이루는 것들 중 최소 비용을 구하는 문제이다. DisjointSet과 MST(Minimum Spanning Tree)를 활용하면 풀 수 있다. 

 

 

C++ 소스코드)

	int kruskal() {
	int ret = 0, cnt = 0;
	vector<pair<int, p>> edges;
	for(int u = 0; u < N; ++u )
	for (auto now : graph[u]) {
	int v = now.first; int cost = now.second;
	edges.push_back({ cost, {u, v} });
	}
	sort(edges.begin(), edges.end());
	Disjointset ds(N + 1);
	for (int i = 0; i < edges.size(); ++i) {
	int cost = edges[i].first;
	if (cost < C) continue;
	int u = edges[i].second.first; int v = edges[i].second.second;
	if (ds.find(u) == ds.find(v)) continue;
	ds.merge(u, v);
	ret += cost;
	cnt++;
	}
	if (cnt != N - 1)
	ret = -1;
	return ret;
	}

view raw 10021.cpp hosted with ❤ by GitHub

 

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/10021_Watering%20the%20Fields.cpp

GitHub - Chocochip101/BOJ_Solution