#include <cstdio>
#include <cstring>
#define oo 21474836

using namespace std;

int g[201][201],gt[201][201];
int dist[201];
int map[201];
bool mark[201]={},noexist[201]={};
int n;

void init()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=n;j++)
				{
					scanf("%d",&g[i][j]);
					if (!g[i][j])
						g[i][j] = oo;
					//printf("%d ",g[i][j]);
				}
			//printf("\n");
		}

	int t,a,b; //read relationship
	scanf("%d",&t);
	for (int i=1;i<=n;i++)
		map[i] = i;
	for (int i=1;i<=t;i++)
		{
			scanf("%d%d",&a,&b);
			int temp;
			while (b!=map[b])
				b = map[b];
			map[b] = a;
		}

	for (int i=1;i<=n;i++) //route compress
		{
			int t = i;
			while (map[t]!=t)
				{
					t = map[t];
				}
			int k = t;
			int temp;
			t = i;
			while (t!=k)
				{
					temp = map[t];
					map[t] = k;
					t = temp;
				}
		}
	
	/*for (int i=1;i<=n;i++)
		printf("%d ",map[i]);*/
	//memcpy(gt,g,sizeof(g));
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			if (i!=j) gt[i][j] = oo;
			else gt[i][j] = 0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			if (g[i][j]<gt[map[i]][map[j]])
				gt[map[i]][map[j]] = g[i][j];
	/*for (int i=1;i<=n;i++)
		{
		for (int j=1;j<=n;j++)
			if (!noexist[i])
			if (!noexist[j])
			{
				printf("%d ",gt[i][j]);
			}
		printf("\n");
		}*/
	for (int i=1;i<=n;i++)
		noexist[i] = (map[i]!=i);
}

void prim()
{
	int min,minj,ans;
	for (int i=1;i<=n;i++)
		dist[i] = oo;
	memcpy(mark,noexist,sizeof(mark));
	int s;
	for (int i=1;i<=n;i++)
		if (!mark[i])
			{
				s = i;
				break;
			}
	/*for (int i=1;i<=n;i++)
		printf("%d ",mark[i]);
	printf("\n");*/
	ans = 0;
	dist[s] = 0;
	for (int i=1;i<=n;i++)
		{
			//printf("111111\n");
			min = oo;
			for (int j=1;j<=n;j++)
				if (!mark[j])
				if (dist[j]<min)
					{
						minj = j;
						min = dist[j];
					}
			//printf("%d %d %d\n",min,minj,ans);
			mark[minj] = 1;
			if (min>=oo) break;
			ans += min;
			for (int j=1;j<=n;j++)
				{
					if (!noexist[j])
					if (gt[minj][j]<dist[j])
						dist[j] = gt[minj][j];
				}
		}
	printf("%d\n",ans);
}

int main()
{
	init();
	prim();
}

• why缩点？？？ (14) lsdnlgd 2010-04-23 08:00:40