POJ 3357 Oreon

問題

無向グラフが与えられるので、その最小全域木を求めよ。
同じコストの最小全域木が複数あるときは、
アルファベット順で最も最初にくるものを求めよ。

制約条件

頂点数≦26

方針

Kruskal法で最小全域木を求めればよい。
辞書順で最初の最小全域木を求めるためには、
枝を、コストが同じものは、頂点の若い順に並べておけばいい。

ソースコード

struct edge{
	int u, v, cost;
	bool operator<(const edge &r)const{
		if(cost!=r.cost)return cost<r.cost;
		return min(u,v)!=min(r.u,r.v)?min(u,v)<min(r.u,r.v):max(u,v)<max(r.u,r.v);
	}
};
int n;
int p[30];
int root(int x){
	if(x==p[x])return x;
	return p[x]=root(p[x]);
}

int main()
{
	int CS;
	scanf("%d",&CS);
	rep(cs,CS){
		scanf("%d",&n);
		vector<edge> es;
		rep(i,n)rep(j,n){
			int d;
			scanf("%d,",&d);
			if(d)es.push_back((edge){ i, j, d } );
		}
		sort(all(es));
		rep(i,n)p[i]=i;
		
		printf("Case %d:\n",cs+1);
		int i=0;
		while(n>1&&i<es.size()){
			int u=es[i].u, v=es[i].v, c=es[i].cost;
			int a=root(u), b=root(v);
			i++;
			if(a==b)continue;
			p[a]=b;
			printf("%c-%c %d\n",min(u,v)+'A',max(u,v)+'A',c);
			n--; i++;
		}
	}
	return 0;
}