pku2421.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 88 行

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct 
{
	int s, e, l;
} Edge;

Edge E[5001];

int hd[101];
int N;

int cp(const void *a, const void *b)
{
	Edge *aa = (Edge *)a;
	Edge *bb = (Edge *)b;
	return aa->l - bb->l;
}

int get_id(int x)
{
	if (hd[x] == 0)
	{
		return x;
	}
	return hd[x] = get_id(hd[x]);
}


int main()
{
	int N, k, i, j, cnt, s, e, sum;
	
	while (scanf("%d", &N) != -1 && N > 0)
	{
		memset(hd, 0, sizeof(hd));
		for (i = 1, cnt = 0; i <= N; i++)
		{
			for (j = 1; j < i; j++)
			{
				E[cnt].s = j;
				E[cnt].e = i;
				scanf("%d", &E[cnt++].l);
			}
			for (j = i; j <= N; j++)
			{
				scanf("%*d");
			}
		}
		scanf("%d", &k);
		i = 1;
		while (k--)
		{
			scanf("%d%d", &s, &e);
			s = get_id(s);
			e = get_id(e);
			if (s != e)
			{
				hd[e] = s;
				i++;
			}
		}
		if (i == N)
		{
			printf("0\n");
			continue;
		}
		qsort(E, cnt, sizeof(E[0]), cp);
		sum = 0;
		for (j = 0; i < N && j < cnt; j++)
		{
			s = get_id(E[j].s);
			e = get_id(E[j].e);
			if (s != e)
			{
				hd[e] = s;
				i++;
				sum += E[j].l;
			}
		}
		printf("%d\n", sum);
	}
	return 0;
}