#include <iostream> 
#include <sstream> 
#include <string> 
#include <vector> 
#include <set> 
#include <map> 
#include <algorithm> 
#include <cstdio> 
#include <cstdlib> 
#include <cmath>
#include <math.h>
#include <string.h>
#include <stdlib.h>
using namespace std; 

#define REP(i, n) for(int i = 0; i<(n); i++) 
#define abs(a) ((a) >= 0 ? (a) : -(a)) 
#define inf 999999999 
typedef vector<int> VI; 
typedef vector<string> VS; 
typedef long long i64; 
typedef unsigned long long u64;

int n, q, v, treenum;
struct edge {
	int x;
	int y;
	int val;
};
struct edge d[5100];
struct village{
	int tree;
};
struct village node[105];

int tree[105][105];


int cmp (const void *a, const void *b)
{
	return ((struct edge *)a)->val - ((struct edge *)b)->val;	
}

void go()
{
	int res = 0;
	for (int i = 0; i < v; i++)
	{
		int a = d[i].x;
		int b = d[i].y;
		if (node[a].tree == 0 && node[b].tree == 0) {
			treenum++;
			node[a].tree = node[b].tree = treenum;
			int j = 0;
		//	while(tree[treenum][j] != -1) j++;
			tree[treenum][j] = a; tree[treenum][j+1] = b;
			res += d[i].val;
		}
		else if (node[a].tree != 0 && node[b].tree == 0) {
			int p = node[a].tree;
			int j = 0;
			node[b].tree = p;
			while(tree[p][j] != -1) j++;
			tree[p][j] = b;
			res += d[i].val;
		}
		else if (node[b].tree != 0 && node[a].tree == 0) {
			int p = node[b].tree;
			int j = 0;
			node[a].tree = p;
			while(tree[p][j] != -1) j++;
			tree[p][j] = a;
			res += d[i].val;
		}	
		else if (node[a].tree !=0 && node[b].tree != 0 && node[a].tree != node[b].tree) {
			int p = node[a].tree;
			int q = node[b].tree;
			int k = 0;
			int j = 0;
			while(tree[p][k] != -1)	k++;
			while(tree[q][j] != -1) {
				node[tree[q][j]].tree = p;
				tree[p][k] = tree[q][j];
				k++;
				j++;	
			}	
			res += d[i].val;
		}
	}
	printf("%ld\n", res);
	
}
int main()
{
	cin>>n;
	v = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			int val;
			cin>>val;
			if (j > i) {d[v].x = i; d[v].y = j; d[v].val = val; v++;}	
		}
	qsort(d, v, sizeof(struct edge), cmp);
	memset(node, 0, sizeof(node));
	memset(tree, -1, sizeof(tree));
	cin>>q;
	treenum = 0;
	for (int i = 0; i < q; i++)
	{	
		int a, b;
		cin>>a>>b;
		a--; b--;
		if (node[a].tree == 0 && node[b].tree == 0) {
			treenum++;
			node[a].tree = node[b].tree = treenum;
			int j = 0;
		//	while(tree[treenum][j] != -1) j++;
			tree[treenum][j] = a; tree[treenum][j+1] = b;
		}	
		else if (node[a].tree != 0 && node[b].tree == 0) {
			int p = node[a].tree;
			int j = 0;
			node[b].tree = node[a].tree;
			while(tree[p][j] != -1) j++;
			tree[p][j] = b;
		}
		else if (node[b].tree != 0 && node[a].tree == 0) {
			node[a].tree = node[b].tree;
			int p = node[b].tree;
			int j = 0;
			while(tree[p][j] != -1) j++;
			tree[p][j] = a;
		}	
		else {
			int p = node[a].tree;
			int q = node[b].tree;
			int k = 0;
			int j = 0;
			while(tree[p][k] != -1)	k++;
			while(tree[q][j] != -1) {
				node[tree[q][j]].tree = p;
				tree[p][k] = tree[q][j];
				k++;
				j++;	
			}	
		}
	}

	go();
}

• 输入里就有可能有环.... (6) direfire 2006-10-17 11:08:40