#include<cstdio>
#include<cstring>
#include<set>
#include<map>
#include<string>
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
#include<sstream>
#include<math.h>
#include<stack>
using namespace std;


#define FOR(i,s,e) for(i = s;i<e;i++)
#define SET(add,v) memset(add,v,sizeof(add))
#define VI vector<int>
#define VS vector<string>
#define ISS istringstream
#define OSS ostringstream
#define  MAX 100
struct node
{
	int id1,id2;
	int length;
}edges[MAX * MAX];
bool operator <(const node &a,const node &b)
{
	if (a.length != b.length)
	{
		return a.length < b.length;
	}
	if (a.id1 != b.id1)
	{
		return a.id1 < b.id1;
	}
	return a.id2 < b.id2;
}
int mapp[MAX][MAX];
int n;
int cnt;
int pre[MAX];
int getHead(int id)
{
	if (id != pre[id])
	{
		pre[id] = getHead(pre[id]);
	}
	return pre[id];
}
int getN(char *tar)
{
	int back = 0;
	while (true)
	{
		if (*tar >= '0' && *tar <= '9')
		{
			back = back * 10 + *tar - '0';
		}
		else
			return back;
		tar++;
	}
}
int main(){
	freopen("in.txt","r",stdin);
	int casei;
	scanf("%d",&casei);
	int i,j;
	int cc = 1;
	while (casei--)
	{
		cnt = 0;
		char tempc;
		FOR(i,0,MAX)
		{
			pre[i] = i;
		}
		cin>>n;
		FOR(i,0,n)
		{
			FOR(j,0,n)
			{
				scanf("%d",&mapp[i][j]);
				scanf("%c",&tempc);
			}
		}
		FOR(i,0,n)
		{
			FOR(j,i + 1,n)
			{
				if (mapp[i][j])
				{
					edges[cnt].id1 = i;
					edges[cnt].id2 = j;
					edges[cnt++].length = mapp[i][j];
				}
			}
		}
		sort(edges,edges + cnt);
		cout<<"Case "<<cc++<<":"<<endl;
		int ccnt = 0;


		FOR(i,0,cnt)
		{
			node tn = edges[i];
			if (getHead(tn.id1) != getHead(tn.id2))
			{
				pre[tn.id1] = getHead(tn.id2);
				edges[ccnt ++] = tn;
			}
			if (ccnt == n - 1)
			{
				break;
			}
		}


		FOR(i,0,n - 1)
		{
			cout<<(char)(edges[i].id1 + 'A')<<'-'<<char(edges[i].id2 + 'A')<<' '<<edges[i].length<<endl;
		}
		cout<<endl;
	}
	return 0;
}

• Re:我用Krus ,给边排序时 先按照边长,再按照节点名称(小端点在前)为什么不对呢??(内附代码) (4) nauhcud 2007-09-02 18:24:44