문제 출처

1. 문제설명

  • N개의 논에 물을 대려고 한다.
  • 물을 대는 방법은 직접 논에 우물을 파거나 이미 물을 대고 있는 다른 논으로부터 물을 끌어오는 법이다.

  • 각각의 논에 대해 우물을 파는 비용과 논들 사이에 물을 끌어오는 비용들이 주어졌을 때 최소 비용을 구하라

  • 문제 분류
    • Graph, MST


2. 알고리즘 설계

  • 최소신장트리 문제이다.
  • 조건이 약간 추가되었다면, 우물을 파는 비용과 우물 간 간선 비용을 모두 처리해야 된다는 것이다.
  • 약간의 트릭을 주었다.
    • 각각의 논을 파는 비용 중에 하나를 반드시 선택해야 한다.
      • 이러한 선택 경우가 N개 있다.(각 논에 대한 우물 파는 비용이 주어지므로)
      • 이 경우를 하나의 정점으로 처리하였다.
      • i번째 우물 비용은 i에서 N+1 정점으로 이동하는 비용으로 처리하면 된다.
        • 즉, adj[i][N+1]=cost 라고 생각하면 되겠다.
  • 이제 비용에 따라 간선을 정렬한다.
  • 정렬된 간선을 하나씩 꺼내면서 최소신장트리를 그려나간다.
    • 만약 N+1개(우물 건설 비용 포함)의 노드가 모두 연결되었다면 종료한다.


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using ti3 = tuple<int,int,int>;

int n, P[302], e, cnt, ans, a, b, cost;
ti3 edge[100'002];

int Find(int x) { return (x == P[x] ? x : Find(P[x])); }
bool Union(int x, int y) {
	x = Find(x);
	y = Find(y);

	if(x == y) return false;
	P[x] = y;
	return true;
}

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

	cin >> n;
	for(int c, i=1; i<=n; i++) {
		cin >> c;
		edge[e++] = {c, i, n+1};
	}

	for(int i=1; i<=n; i++) {
		P[i] = i;
		for(int c, j=1; j<=n; j++) {
			cin >> c;
			if(i >= j) continue;
			edge[e++] = {c, i, j};
		}
	}
	n += 1;
	sort(edge, edge + e);

	for(int i=0; i<e; i++) {
		tie(cost, a, b) = edge[i];
		if(Union(a, b)) {
			ans += cost;
			cnt++;
			if(cnt == n) break;
		}
	}

	cout << ans;

	return 0;
}