More actions
({CREATE}) |
No edit summary |
||
| Line 2: | Line 2: | ||
= 오늘의 문제 = | = 오늘의 문제 = | ||
* [https://www.acmicpc.net/problem/1197|최소 스패닝 트리] | * ~~[https://www.acmicpc.net/problem/1197|최소 스패닝 트리]~~ | ||
* 변경 : [https://www.acmicpc.net/problem/1922|네트워크 연결] | |||
* 변경사유 : N의 크기가 커서 O(N^2)에 풀 수 없어서.. | |||
~~힙을 이용하면 되지만 아직 저희의 실력에 그것을 구현하기는 힘들어서..~~ | |||
= 참가자 = | = 참가자 = | ||
* | * 박인서 | ||
= 코드 = | = 코드 = | ||
| Line 11: | Line 14: | ||
== 박인서 == | == 박인서 == | ||
#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; | |||
} | |||
== 곽정흠 == | == 곽정흠 == | ||
| Line 18: | Line 55: | ||
== 박인서 == | == 박인서 == | ||
* 프림 알고리즘을 이용하였습니다. ~~크루스칼로 구현하기 위해서는 Union Find를 구현해야 되는데 이해가 안가서..~~ | |||
* 자세한 사항은 [https://ko.wikipedia.org/wiki/%ED%94%84%EB%A6%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98|프림 알고리즘-위키피디아] 참조 | |||
== 곽정흠 == | == 곽정흠 == | ||
Revision as of 04:39, 20 September 2016
오늘의 문제
~~힙을 이용하면 되지만 아직 저희의 실력에 그것을 구현하기는 힘들어서..~~
참가자
- 박인서
코드
15이원준
박인서
#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;
}
곽정흠
아이디어
15이원준
박인서
- 프림 알고리즘을 이용하였습니다. ~~크루스칼로 구현하기 위해서는 Union Find를 구현해야 되는데 이해가 안가서..~~
- 자세한 사항은 알고리즘-위키피디아 참조