[백준 6497] 전력난

문제 풀이

 

모든 두 집 쌍에 대해서 불이 켜진 길로만 서로를 왕래할 수 있도록 해야 하며, 위 조건을 지키면서 절약할 수 있는 최대 액수를 구하는 문제입니다.

 

모든 두 집 쌍에 대해서 가로등을 켜면서(연결하면서) 최소의 비용으로 만들고 싶다면 MST를 구하라는 문제입니다.

그런데 절약할 수 있는 최대 액수를 물었으므로 [전체의 비용 - MST를 만드는 비용 = 최대 액수]로 구해주면 됩니다.

 

최종 비용을 계산할 때 보통은 최소의 비용을 구하라고 하지만 반대로 얼마큼 절약할 수 있는지를 물어보는 문제였습니다.

 

소스 코드

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

const int MAX = 200001;
int parent[MAX];
vector<pair<int, pair<int, int> > > edges;
int m, n, totalCost;

void input()
{
	edges.clear();

	totalCost = 0; // 전체 비용
	for (int i = 0; i < n; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;
		totalCost += z;
		edges.push_back({ z, {x,y} });
	}

	sort(edges.begin(), edges.end());
	for (int i = 1; i <= m; i++) parent[i] = i;
}

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

void unionParent(int a, int b)
{
	a = findParent(a);
	b = findParent(b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
}

void kruskal()
{
	int size = static_cast<int>(edges.size());
	int useCost = 0; // MST 만드는 비용
	for (int i = 0; i < size; i++)
	{
		int cost = edges[i].first;
		int a = edges[i].second.first;
		int b = edges[i].second.second;
		if (findParent(a) != findParent(b))
		{
			unionParent(a, b);
			useCost += cost;
		}
	}

	cout << totalCost - useCost << endl;
}

void solve()
{
	while (true)
	{
		cin >> m >> n;
		if (m == 0 && n == 0) break;
		input();
		kruskal();
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}