1R/2016 09 16

오늘의 문제

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

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

참가자

• 박인서

코드

15이원준

#include<iostream>
#include<vector>

using namespace std;
typedef struct node {
	int s, e, v;
	node(int a, int b, int c) {
		s = a;
		e = b;
		v = c;
	}
}node;

int visit[1010] = { 0, };
vector<node> in;
vector<int> checked;
int N, M;

bool choose(int e) {
	if ((visit[in[e].e] == 1 && visit[in[e].s] == 1) || (visit[in[e].e] == 0 && visit[in[e].s] == 0)) {
		return false;
	}
	return true;
}

int main() {

	cin >> N >> M;
	for (int i = 0; i<M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		in.push_back(node(a, b, c));
	}
	for (int i = 0; i<N - 1; i++) {
		int min = -1;
		for (int j = 0; j<M; j++) {
			if ((checked.size() == 0 || choose(j)) && (min == -1 || in[min].v > in[j].v)) {
				min = j;
			}
		}
		visit[in[min].s] = 1;
		visit[in[min].e] = 1;
		checked.push_back(min);
	}
	int answer = 0;
	for (int i = 0; i<N - 1; i++) {
		answer += in[checked[i]].v;
	}
	cout << answer << endl;
}

박인서

#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를 구현해야 되는데 이해가 안가서..~~
• 자세한 사항은 알고리즘-위키피디아 참조