[백준 2406] 안정적인 네트워크 (C++)

문제 링크: https://www.acmicpc.net/problem/2406

2406번: 안정적인 네트워크

1. 주의할 점

- 1번 Node를 제외하고 MST를 만든다

- 총 Node-2개의 간선이 만들어지면 된다(Cycle을 생성하는 간선은 개수에 포함 안함)

 

2. 구현

- 크루스칼 알고리즘을 통해 MST 문제를 해결한다

- 이미 연결된 지사의 컴퓨터 중, 같은 부모를 공유하고 있지 않다면 Make_union(a,b) 함수를 통해 같은 부모를 공유하도록 설정하고, Cnt++한다

- 입력받는 배열에 대해 1번 Node를 제외하고, i<j 인 배열만 간선으로 우선순위 큐에 저장한다(양방향이므로 한쪽만 더해주면 된다)

- 만약 Cnt==Node-2라면 0 0을 출력하고 끝내고, 아니라면 크루스칼 알고리즘을 수행하며 새로운 간선이 추가되면 Cnt++하고, Cnt==Node-2가 되면 While문을 종료하고 정답을 출력한다

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct info {
	int start, end, val;
};
struct cmp {
	bool operator()(info &a, info &b) {
		return a.val > b.val;
	}
};
info tmp;
int node, edge, s, e, val;
int par[1001], arr[1001][1001];
bool check[1001] = { false, };
vector<info> v;

int find_parent(int x){
	if (par[x] == x) return x;
	return par[x] = find_parent(par[x]);
}

void make_union(int a, int b) {
	a = find_parent(a);
	b = find_parent(b);
	if (a < b) par[b] = a;
	else if (a > b) par[a] = b;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> node >> edge;
	for (int i = 1; i <= node; i++)
		par[i] = i;
	int cnt = 0;
	for (int i = 0; i < edge; i++) {
		cin >> s >> e;
		if (find_parent(s) != find_parent(e)) {
			make_union(s, e);
			cnt++;
		}
	}
	priority_queue<info, vector<info>, cmp> pq;
	for (int i = 1; i <= node; i++) {
		for (int j = 1; j <= node; j++) {
			cin >> arr[i][j];
			if (i>1 && i < j) {
				tmp.start = i;
				tmp.end = j;
				tmp.val = arr[i][j];
				pq.push(tmp);
			}
		}
	}
	long long result = 0;
	if (cnt == node - 2) {
		cout << result << " " << v.size();
	}
	else {
		while (!pq.empty()) {
			int cs = pq.top().start;
			int ce = pq.top().end;
			int cv = pq.top().val;
			pq.pop();
			int ps = find_parent(cs);
			int pe = find_parent(ce);
			if (ps == pe) continue;
			cnt++;
			make_union(cs, ce);
			result += cv;
			tmp.start = cs;
			tmp.end = ce;
			v.push_back(tmp);
			if (cnt == node - 2) break;
		}
		cout << result << " " << v.size() << '\n';
		for (int i = 0; i < v.size(); i++) {
			cout << v[i].start << " " << v[i].end << '\n';
		}
	}
	system("pause");
	return 0;
}