pku1679.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

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

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

Edge eg[11000];
int ueid[110], un[110];
int m, n;

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

int get_id(int x)
{
	int root;
	if (un[x] == x)
	{
		return x;
	}
	root = get_id(un[x]);
	un[x] = root;
	return root;
}

int kru()
{
	int i, j, total;
	total = 0;
	for (i = 1; i <= n; i++)
	{
		un[i] = i;
	}
	for (i = 0, j = 0; j < n - 1 && i < m; i++)
	{
		if (get_id(eg[i].s) != get_id(eg[i].e))
		{
			total += eg[i].v;
			ueid[j] = i;
			un[get_id(eg[i].e)] = get_id(eg[i].s);
			j++;
		}
	}
	return total;
}

int kru2(int p)
{
	int i, j, total;
	total = 0;
	for (i = 1; i <= n; i++)
	{
		un[i] = i;
	}
	for (i = 0, j = 0; j < n - 1 && i < m; i++)
	{
		if (i == p)
		{
			continue;
		}
		if (get_id(eg[i].s) != get_id(eg[i].e))
		{
			total += eg[i].v;
			un[get_id(eg[i].e)] = get_id(eg[i].s);
			j++;
		}
	}
	if (j != n - 1)
	{
		return -10000;
	}
	return total;
}


int main()
{
	int T, s, e, i, v, total, tmpt;
//	freopen("PKU1679.in", "r", stdin);
	scanf("%d", &T);

	while (T--)
	{
		scanf("%d%d", &n, &m);
		for (i = 0; i < m; i++)
		{
			scanf("%d%d%d", &s, &e, &v);
			eg[i].s = s;
			eg[i].e = e;
			eg[i].v = v;
		}

		qsort(eg, m, sizeof(eg[0]), cmp);
		
		total = kru();

		for (i = 0; i < n - 1; i++)
		{
			tmpt = kru2(ueid[i]);
			if (total == tmpt)
			{
				printf("Not Unique!\n");
				break;
			}
		}
		if (i == n - 1)
		{
			printf("%d\n", total);
		}
	}
}