#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define NMAX 105
struct Edge {
	int s, e, v;
	bool operator<(const Edge& e) const {
		return v < e.v;
	}
}edge[NMAX * NMAX];
int N, Q, cur;
int vset[NMAX];
int kruskal()
{
	int i, j, sum = 0, V1, V2;
	j = 0;
	while(cur < (N - 1))
	{
		V1 = edge[j].s;
		V2 = edge[j].e;
		if(vset[V1] != vset[V2])
		{
			sum += edge[j].v;
			cur++;
			for(i=1; i<=N; i++)
				if(vset[i] == vset[V2])
					vset[i] = vset[V1];
		}
		j++;
	}
	return sum;
}
int main() {
//freopen("in.txt", "r", stdin);
	int i, j, r, k;
	while(scanf("%d", &N) != EOF) {
		for(i=1; i<=N; i++)
			vset[i] = i;
		r = 0;
		k = 1;
		for(i=1; i<=N; i++) {
			++k;
			for(j=1; j<k; j++)
				scanf("%*d");
			for(; j<=N; j++) {
				edge[r].s = i;
				edge[r].e = j;
				scanf("%d", &edge[r++].v);
			}
		}
		scanf("%d", &Q);
		int a, b;
		cur = 0;
		while(Q--) {
			scanf("%d%d", &a, &b);
			if(vset[a] != vset[b]) {
				for(i=1; i<=N; i++)
					if(vset[i] == vset[a])
						vset[i] = vset[b];
				cur++;
			}
		}
		sort(edge, edge + r);
		printf("%d\n", kruskal());
	}
	return 0;
}

• Re:kruskal 为什么WA??? (175) smwwh 2010-09-23 16:43:55
  • Re:kruskal 为什么WA??? (59) huangwei_njust 2011-02-14 22:08:03