[백준/BOJ] 백준 2463번 : 비용

www.acmicpc.net/problem/2463

2463번: 비용

유니온 파인드를 이용해 문제를 해결했다. 간선을 가중치가 큰 순서로 정렬하고, 가중치가 큰 간선부터 확인하여 그 간선에 속한 정점의 그룹이 다르다면 해당 간선이 끊어지는 경우일 때 두 정점 사이의 경로가 없어지게 됨을 고려해서 문제를 해결했다 그리고 이때 두 그룹을 합쳤다.  group_size에 해당 그룹에 속한 정점의 개수를 저장했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <cmath>
#include <set>
using namespace std;

int n, m;
vector<int> parent(100001);
vector<pair<int, pair<int, int>>> adj;
vector<int> rank_size(100001);
vector<long long> group_size(100001); //해당 그룹에 속한 정점의 개수 저장

void Pre()
{
	for (int i = 1; i <= n; i++)
	{
		parent[i] = i;
		rank_size[i] = 1;
		group_size[i] = 1;
	}
}

int Find(int u)
{
	if (u == parent[u])
		return u;

	return parent[u] = Find(parent[u]);
}

void Merge(int u, int v)
{
	u = Find(u);
	v = Find(v);

	if (u != v)
	{
		if (rank_size[u] < rank_size[v])
		{
			parent[u] = v;

			//더해지는 그룹에 속한 정점의 개수를 추가한다
			group_size[v] += group_size[u];
		}

		else
		{
			parent[v] = u;

			if (rank_size[u] == rank_size[v])
				rank_size[u]++;

			//더해지는 그룹에 속한 정점의 개수를 추가한다
			group_size[u] += group_size[v];
		}
	}
}

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

	long long total_cost = 0;
	cin >> n >> m;

	Pre();
	for (int i = 0; i < m; i++)
	{
		int x, y, w;

		cin >> x >> y >> w;
		adj.push_back(make_pair(w, make_pair(x, y)));

		total_cost += w;
	}

	sort(adj.begin(), adj.end());
	reverse(adj.begin(), adj.end()); //간선의 가중치가 큰 순서로 정렬하기 위해 sort한것을 뒤집는다

	long long add_cost = total_cost;
	long long result = 0;

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

		u = Find(u);
		v = Find(v);

		long long cost = adj[i].first;

		if (Find(u) != Find(v)) //이때 끊어지는 경우일때 (이게 끊어져야 끊어지는 경우일때)
		{
			result = (result + (group_size[u] * group_size[v] * add_cost) + 1000000000) % 1000000000;
			Merge(u, v);
		}

		add_cost = (add_cost - cost + 1000000000) % 1000000000;
	}

	cout << result;

	return 0;
}