pku1861.cpp

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

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

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

Edge E[15001], u[1001];
int N, M;
int nd[1001];

int Min(int x, int y)
{
	return (x < y) ? x : y;
}

int Max(int x, int y)
{
	return (x > y) ? x : y;
}

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

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

int main()
{
	int i, j, s, e, hds, hde;
	scanf("%d%d", &N, &M);
	memset(nd, 0, sizeof(nd));
	for (i = 0; i < M; i++)
	{
		scanf("%d%d", &s, &e);
		E[i].s = Min(s, e);
		E[i].e = Max(s, e);
		scanf("%d", &E[i].l);
	}
	qsort(E, M, sizeof(E[0]), cp);
	for (i = 0, j = 0; i < N - 1 && j < M; j++)
	{
		hds = get_id(E[j].s);
		hde = get_id(E[j].e);
		if (hds != hde)
		{
			nd[hde] = hds;
			u[i].s = E[j].s;
			u[i].e = E[j].e;
			i++;
			if (i == N - 1)
			{
				printf("%d\n", E[j].l);
			}
		}
	}
	printf("%d\n", N - 1);
	qsort(u, N - 1, sizeof(u[0]), cp);
	for (i = 0; i < N - 1; i++)
	{
		printf("%d %d\n", u[i].s, u[i].e);
	}
	return 0;
}