#include <iostream>
#include <cstdio>
#include <memory>
#include <map>
#include <utility>

using namespace std;

const int MaxN = 100000;

int N, M;
int IDs[MaxN];
map<int, int> IDMarks;
int FilePos[MaxN];
int DSet[MaxN];
int Len, Limit;
int Queue[MaxN * 2];
int InDegs[MaxN * 2];
int* InEdges[MaxN * 2];
int* InValues[MaxN * 2];
int Sours[MaxN * 2];
int Belongs[MaxN * 2];
int Choices[MaxN * 2];
int ChoiceValues[MaxN * 2];
int Wastes[MaxN * 2];
int Result;
int* Subsets[MaxN];
int SetSizes[MaxN];
int Results[MaxN];

int find_father(int P[], int V)
{
	int F = V;
	while (P[F] != F) F = P[F];
	while (P[V] != F)
	{
		int Temp = P[V];
		P[V] = F;
		V = Temp;
	}
	return F;
}

void join_to(int P[], int V1, int V2)
{
	P[find_father(P, V1)] = find_father(P, V2);
}

template<class type>
type* clone(const type* Sour, size_t Size)
{
	type* P = new type[Size];
	memcpy(P, Sour, Size * sizeof(type));
	return P;
}

void input()
{
	int I, J, A, B;
	char Ch;

	fseek(stdin, 0, SEEK_SET);
	J = 0;
	for (;;)
	{
		Ch = getchar();
		if (Ch == '\n') break;
		if (Ch <= ' ') J = 0;
		else if (J == 0) N++, J = 1;
	}
	N--;

	fseek(stdin, 0, SEEK_SET);
	for (I = 0; I < N; I++) DSet[I] = I, InDegs[I] = 0;
	scanf(" %*s");
	IDMarks.clear();
	for (I = 0; I < N; I++)
	{
		scanf("%d", &IDs[I]);
		IDMarks[IDs[I]] = I;
	}
	for (I = 0; I < N; I++)
	{
		scanf("%d", &J);
		A = IDMarks[J];
		FilePos[A] = ftell(stdin);
		for (B = 0; B < N; B++)
			if (A != B)
			{
				scanf("%d", &J);
				if (J != 0)
				{
					join_to(DSet, A, B);
					InDegs[B]++;
				}
			}
			else
				scanf(" %*s");
	}
}

void init_tree()
{
	int I, J, A, B;
	for (I = 0; I < Len; I++)
	{
		A = Queue[I];
		InEdges[A] = new int[InDegs[A]];
		InValues[A] = new int[InDegs[A]];
		InDegs[A] = 0;
		Sours[A] = A;
		Belongs[A] = A;
		Choices[A] = -1;
		Wastes[A] = 0;
	}
	for (I = 0; I < Len; I++)
	{
		A = Queue[I];
		fseek(stdin, FilePos[A], SEEK_SET);
		for (B = 0; B < N; B++)
			if (B != A)
			{
				scanf("%d", &J);
				if (J != 0)
				{
					InEdges[B][InDegs[B]] = A;
					InValues[B][InDegs[B]++] = J;
				}
			}
			else
				scanf(" %*s");
	}
}

void done_tree()
{
	int I;
	for (I = 0; I < Len; I++)
	{
		delete[] InEdges[Queue[I]];
		delete[] InValues[Queue[I]];
	}
}

bool perform_point(int Index, int V)
{
	int I, J, U, Temp;
	int Deg;
	static int Edges[MaxN * 2];
	static int Values[MaxN * 2];
	Temp = 0x7fffffff;
	U = -1;
	for (I = 0; I < InDegs[V]; I++)
		if (InValues[V][I] < Temp)
			Temp = InValues[V][I], U = I;
	if (U < 0) return false;
	U = InEdges[V][U];
	Result += Temp;
	if (Index >= Limit) Wastes[V] += Temp;
	ChoiceValues[V] = Temp;
	U = find_father(Belongs, U);
	if (find_father(Sours, U) != V)
	{
		Choices[V] = U;
		join_to(Sours, V, U);
	}
	else
	{
		Sours[M] = M;
		Belongs[M] = M;
		Choices[M] = -1;
		Wastes[M] = 0;
		for (V = U; V >= 0; V = Choices[V])
		{
			V = find_father(Belongs, V);
			Sours[V] = M;
			if (Wastes[V] > Wastes[M]) Wastes[M] = Wastes[V];
		}
		Deg = 0;
		for (V = U; V >= 0; V = Choices[V])
		{
			V = find_father(Belongs, V);
			join_to(Belongs, V, M);
			for (I = 0; I < InDegs[V]; I++)
			{
				J = InEdges[V][I];
				J = find_father(Belongs, J);
				if (Sours[J] != M)
				{
					Edges[Deg] = J;
					Values[Deg++] = InValues[V][I] - ChoiceValues[V];
				}
			}
			delete[] InEdges[V];
			delete[] InValues[V];
			InEdges[V] = 0;
			InValues[V] = 0;
		}
		InDegs[M] = Deg;
		InEdges[M] = clone(Edges, Deg);
		InValues[M] = clone(Values, Deg);
		Queue[Len++] = M;
		M++;
	}
	return true;
}

int perform_tree()
{
	int I;
	if (Len == 1) return 0;
	init_tree();
	Limit = Len;
	M = N;
	Result = 0;
	for (I = 0; I < Len; I++)
		if (!perform_point(I, Queue[I])) break;
	if (I < Len - 1 || Len == Limit) return -1;
	Result -= Wastes[Queue[Len - 1]];
	done_tree();
	return Result;
}

void perform()
{
	int I, J, F;
	static int Lasts[MaxN];
	static int Nexts[MaxN];
	static bool Marks[MaxN];
	memset(Lasts, -1, sizeof Lasts);
	memset(Nexts, -1, sizeof Nexts);
	memset(Marks, false, sizeof Marks);
	for (I = 0; I < N; I++)
	{
		F = find_father(DSet, I);
		if (Lasts[F] >= 0) Nexts[Lasts[F]] = I;
		else Marks[I] = true;
		Lasts[F] = I;
		Subsets[I] = 0;
	}
	for (I = 0; I < N; I++)
		if (Marks[I])
		{
			Len = 0;
			J = I;
			while (J >= 0)
			{
				Queue[Len++] = J;
				J = Nexts[J];
			}
			SetSizes[I] = Len;
			Subsets[I] = clone(Queue, Len);
			Results[I] = perform_tree();
			if (Results[I] < 0)
			{
				printf("NONE\n");
				return;
			}
		}
	for (I = 0; I < N; I++)
		if (Marks[I])
		{
			for (J = 0; J < SetSizes[I]; J++)
				printf("%d ", IDs[Subsets[I][J]]);
			printf("%d\n", Results[I]);
		}
}

int main()
{
	freopen("sites.txt", "rb", stdin);
	input();
	perform();
	return 0;
}

• 好程序！等价类用得巧，写得已经很简洁了，虽然没有注释没有完全看懂，也值得放在POJ做纪念啦 (5538) atlas_of_rruucc 2005-09-28 19:54:45