U E D R , A S I H C RSS

1R/2016_09_16 (rev. 1.2)

1R/2016_09_16



1. 오늘의 문제

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

2. 참가자

  • 박인서

3. 코드

3.1. 15이원준


3.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;
}

3.3. 곽정흠


4. 아이디어

4.1. 15이원준


4.2. 박인서

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

4.3. 곽정흠

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:07
Processing time 0.0209 sec