[boj : 1833] 고속철도 설계하기

www.acmicpc.net/problem/1833

1833번: 고속철도 설계하기

문제 : 이미 설치되어 있는 철도가 있고 새로 지어야 되는 철도가 주어진다. 이때 (이미 지어진 철도의 가중치) + (새로 지어야 되는 철도의 가중치)의 최소값을 구해라

 

해설 : 입력값이 음수로 들어오면 이미 연결되어있으니깐 정답에 더해주고 부모들을 합쳐준다. 나머지는 그냥 평범한 mst 문제

 

#include<bits/stdc++.h>

using namespace std;

struct info {
	int x, y, w;
	bool operator<(const info& cur) const {
		return w < cur.w;
	}
};

int n;
int graph[210][210];
int parent[201];
vector<info> v;

bool check_parent(int x, int y);
void union_parent(int x, int y);
int get_parent(int x);

int main()
{
	int ans = 0;
	cin >> n;
	for (int i = 1; i <= n; i++)parent[i] = i;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) 
			cin >> graph[i][j];
	for(int i=1;i<=n;i++)
		for (int j = i; j <= n; j++) {
			if (graph[i][j] < 0) {
				union_parent(i, j);
				ans += abs(graph[i][j]);
			}
			else if (graph[i][j] > 0)
				v.push_back({ i,j,graph[i][j] });
		}
	sort(v.begin(), v.end());
	vector<pair<int, int>> edge;
	for (int i = 0; i < v.size(); i++) {
		int x = v[i].x;
		int y = v[i].y;
		if (!check_parent(x, y)) {
			union_parent(x, y);
			ans += v[i].w;
			edge.push_back({ x,y });
		}
	}
	cout << ans<<" "<<edge.size()<<"\n";
	for (auto u : edge)
		cout << u.first << " " << u.second << "\n";
	return 0;
}
bool check_parent(int x, int y)
{
	x = get_parent(x);
	y = get_parent(y);

	if (x == y)return true;
	return false;
}
void union_parent(int x, int y)
{
	x = get_parent(x);
	y = get_parent(y);

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