[백준/BOJ] 백준 6497번 : 전력난

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

6497번: 전력난

크루스칼 알고리즘을 이용하여 최소 스패닝 트리 간선들의 가중치 합을 구했다. 그리고 현재 비용 - 최소 스패닝 트리 간선들의 가중치 합을 통해 절약할 수 있는 최대 비용을 구했다.

 

코드

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

int m, n;
vector<pair<int,int>> adj[200000]; //pair: 가중치, 연결정점
int parent[200000];
int rank_size[200000];

//유니온 파인드의 파인드
int find(int node)
{
	if (parent[node] == node)
		return node;

	return parent[node] = find(parent[node]);
}

//유니온 파인드의 유니온
void merge(int node1, int node2)
{
	node1 = find(node1);
	node2 = find(node2);

	if (node1 == node2)
		return;

	if (rank_size[node1] < rank_size[node2])
		parent[node1] = node2;
	
	else
	{
		parent[node2] = node1;

		if (rank_size[node1] == rank_size[node2])
			rank_size[node1]++;
	}

}

//최소 스패닝 트리 간선의 가중치 합을 구한다
int Solve()
{
	int ret = 0;

	vector<pair<int, pair<int, int>>> edge;

	for(int i=0; i< m; i++)
		for (int j = 0; j < adj[i].size(); j++)
		{
			int u = i;
			int v = adj[i][j].second;
			int cost = adj[i][j].first;

			//그래프의 간선들을 모두 저장한다
			edge.push_back(make_pair(cost, make_pair(u, v)));
		}

	//간선을 가중치의 오름차순으로 정렬한다
	sort(edge.begin(), edge.end());

	for (int i = 0; i < edge.size(); i++)
	{
		int u = edge[i].second.first;
		int v = edge[i].second.second;

		if (find(u) != find(v))
		{
			merge(u, v);

			//최소 스패닝 트리 간선의 가중치의 합을 구한다
			ret += edge[i].first;
		}
	}

	return ret;
}

void pre()
{
	for (int i = 0; i < m; i++)
	{
		parent[i] = i;
		adj[i].clear();
	}

	memset(rank_size, 0, sizeof(rank_size));
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int x, y, z;
	int total_cost;

	while (1)
	{
		cin >> m >> n;

		pre();

		if (m == 0 && n == 0)
			break;

		total_cost = 0;

		for (int i = 0; i < n; i++)
		{
			cin >> x >> y >> z;

			adj[x].push_back(make_pair(z, y));
			adj[y].push_back(make_pair(z, x));

			total_cost += z;
		}

		//현재의 비용 - 최소 스패닝트리 간선들의 가중치합
		cout << total_cost - Solve() <<"\n";
	}

	return 0;
}