hdu 1233はやはり融通工事(最小生成樹、prm、優先列、kruskyalそして検索集)
2735 ワード
テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1233
1、prm
優先列でいつもWAと書いたら、n=1がないことに気づき、困っていました。
1、prm
優先列でいつもWAと書いたら、n=1がないことに気づき、困っていました。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int N;
int vis[110];
int map[110][110];
struct node {
int x, y, dis;
friend bool operator < (node a, node b) {
return a.dis > b.dis;
}
};
int cnt = 0, ans = 0;
int main() {
//freopen("input.txt", "r", stdin);
while(~scanf("%d", &N) && N) {
if(N == 1) {
printf("0
");
continue;
}
cnt = N;
ans = 0;
int i;
int x, y, z;
memset(map, 0, sizeof(map));
for(i = 0; i < N * (N - 1) / 2; i++) {
scanf("%d %d %d", &x, &y, &z);
map[x][y] = z;
map[y][x] = z;
}
memset(vis, 0, sizeof(vis));
priority_queue <node> q;
node now, next;
for(i = 1; i <= N; i++) {
if(map[1][i]) {
now.x = 1, now.y = i, now.dis = map[1][i];
q.push(now);
}
}
vis[1] = 1;
cnt--;
while(!q.empty()) {
now = q.top();
q.pop();
if(vis[now.y] == 1) continue;
vis[now.y] = 1;
ans += now.dis;
cnt--;
if(cnt == 0) {
printf("%d
", ans);
break;
}
int i;
for(i = 1; i <= N; i++) {
if(map[now.y][i] && vis[i] == 0) {
next.x = now.y, next.y = i, next.dis = map[next.x][next.y];
q.push(next);
}
}
}
}
return 0;
}
2、kruskyal:#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m;
struct node {
int s, e, w;
}edge[5050];
int f[5050];
int cmp(node a, node b) {
return a.w < b.w;
}
int find(int x) {
if(f[x] == -1) return x;
return f[x] = find(f[x]);
}
int main() {
while(~scanf("%d", &n) , n) {
m = n * (n - 1) / 2;
int i;
int s, e, w;
for(i = 1; i <= m; i++) {
scanf("%d %d %d", &s, &e, &w);
edge[i].s = s, edge[i].e = e, edge[i].w = w;
}
memset(f, -1, sizeof(f));
sort(edge + 1, edge + m + 1, cmp);
int sum = 0;
for(i = 1; i <= m; i++) {
int t1 = find(edge[i].s);
int t2 = find(edge[i].e);
if(t1 != t2) {
f[t1] = t2;
sum += edge[i].w;
}
}
printf("%d
", sum);
}
return 0;
}