1R/2016 09 16

오늘의 문제

• ~~스패닝 트리~~
• 변경 : 연결
• 변경사유 : N의 크기가 커서 O(N^2)에 풀 수 없어서..

~~힙을 이용하면 되지만 아직 저희의 실력에 그것을 구현하기는 힘들어서..~~

참가자

• 박인서

코드

박인서

#include <iostream>
#include <vector>
#include <algorithm>
typedef std::pair<int, int> pair_int;
std::vector<pair_int> g[10001];
bool visit[10001];

int main()
{
	int n, m, res = 0;
	std::cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		std::cin >> a >> b >> c;
		g[a].push_back(pair_int(b, c));
		g[b].push_back(pair_int(a, c));
	}
	visit[1] = true;
	for (int i = 1; i < n; i++) {
		int x, y, min = 217483647;
		for (int j = 1; j <= n; j++) {
			if (visit[j]) {
				for (int k = 0; k < g[j].size(); k++) {
					if (!visit[g[j][k].first] && g[j][k].second < min)
						min = g[j][k].second, x = j, y = g[j][k].first;
				}
			}
		}
		visit[y] = true;
		res += min;
	}
	std::cout << res;
	return 0;
}

아이디어

박인서

• 프림 알고리즘을 이용하였습니다. ~~크루스칼로 구현하기 위해서는 Union Find를 구현해야 되는데 이해가 안가서..~~
• 자세한 사항은 알고리즘-위키피디아 참조