Baekjoon 2463 비용

Link https://www.acmicpc.net/problem/2463

소스결과 3948 KB / 44 ms

출처 Baekjoon, 한국정보올림피아드 지역본선 2001 중/고등부

언어 C++ 17

분류 Disjoint-Set

 

설명

정점과 가중치가 있는 간선으로 이루어져있는 그래프에서 특정 방식으로 된 연산을 진행 할 때 연산의 총 합을 구하는 프로그램을 작성하자

 

처음에 봤을 때 이해가 조금 안됬던 문제. 연산은 쉽게 이해가 가지만 총 합이라는 의미가 이해가 잘 안갔었다.

결론은 주어지는 모든 정점 중 2개의 점을 선택하는 경우에 대한 연산의 총 합을 구하는 문제.

앞 문제와 같이 해결 방식을 순차적 방법으로 해결 하는 것 보다 역순으로 가중치 총합을 이용하는 방법으로 해결 했다.

또한 역순으로 진행 하면서 집합이 합쳐 질 때, 경우의 수가 1이 아니기에 연산합 * 경우의 수 만큼을 계산 해야 했다.

 

출력 조건에서 총 합이 10^9보다 큰걸 보아하니 변수 범위를 long long으로 확장 시켜 계산 해야 한다.

 

소스코드

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

using namespace std;

const int DIV = 1000000000;

class DisJointSet
{
	int size;
	vector<int> parent;
	vector<int> childs;

public:
	DisJointSet(int size) : size(size) {
		parent.resize(size);
		childs.resize(size);

		for (int i = 0; i < size; i++) {
			parent[i] = i;
			childs[i] = 1;
		}
	};

	int getChilds(int x)
	{
		return childs[find(x)];
	}

	int find(int v) {
		if (parent[v] == v) return v;

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

	bool merge(int x, int y) {

		int px = find(x);
		int py = find(y);

		if (px == py)
			return false;

		parent[px] = py;
		childs[py] += childs[px];

		return true;
	}
};
struct Edge {
	int x, y, cost;

	bool operator<(Edge &e) {
		return cost < e.cost;
	}
};

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

	int n, m;
	long long costSum = 0;
	long long sum = 0;
	cin >> n >> m;

	DisJointSet dis(n + 1);
	vector<Edge> edges(m + 1);

	for (int i = 0; i < m; i++)
	{
		cin >> edges[i].x >> edges[i].y >> edges[i].cost;

		costSum += edges[i].cost;
	}

	sort(edges.begin(), edges.end());

	for (int i = m; i >= 0; i--)
	{
		long long xChilds = dis.getChilds(edges[i].x);
		long long yChilds = dis.getChilds(edges[i].y);

		if (dis.find(edges[i].x) != dis.find(edges[i].y))
		{
			sum += (costSum * (xChilds * yChilds));
			sum %= DIV;

			dis.merge(edges[i].x, edges[i].y);
		}
		costSum -= edges[i].cost;		
	}

	cout << sum % DIV;

	return 0;
}