hdu 1233はやはり融通工事(最小生成樹、prm、優先列、kruskyalそして検索集)

2735 ワード

テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1233
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; }