#include <cstdio>
#include <ctype.h>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF=0x7fffffff;
struct edge{
	int st,ed,val;
} bian[1024];
struct Dist{
	int vex,val;
} g[64];
int n,pos,d[64][64];
bool vst[64];
bool cmp(edge x,edge y){
	if(x.val<y.val) return true;
	if(x.val>y.val) return false;
	if(x.st<y.st) return true;
	if(x.st>y.st) return false;
	if(x.ed<y.ed) return true;
	return false;
}
void make_bian(int s,int e,int val){
	if(s>e){
		bian[pos].st=e;
		bian[pos].ed=s;
	}else{
		bian[pos].st=s;
		bian[pos].ed=e;
	}
	bian[pos].val=val;
	pos++;
}
void prim(int st){
	int i,j,mn,px;
	for(i=0;i<n;i++){
		g[i].val=d[st][i];
		g[i].vex=st;
	}
	vst[st]=true;
	for(i=1;i<n;i++){
		mn=INF;
		for(j=0;j<n;j++)
			if(!vst[j]){
				if(g[j].val<mn){
					mn=g[j].val;
					px=j;
				}else if(g[j].val==mn){
					int min_e=min(g[px].vex,px);
					int min_n=min(g[j].vex,j);
					if(min_e>min_n) px=j;
					else if(min_e==min_n){
						int	max_e=max(g[px].vex,px);
						int max_n=max(g[j].vex,j);
						if(max_e>max_n) px=j;
					}
				}
			}
		vst[px]=true;
		make_bian(px,g[px].vex,mn);
		for(j=0;j<n;j++)
			if(!vst[j]&&d[px][j]<g[j].val){
				g[j].val=d[px][j];
				g[j].vex=px;
			}
	}
}
int main()
{
	int t,i,j,tmp,cases=0;
	char ch;
	scanf("%d",&t);
	while(t--){
		scanf("%d\n",&n);
		i=j=0;
		while(1){
			while((ch=getchar())==' '||ch==',');
			if(ch=='\n') j=0,i++;
			if(i==n) break;
			ungetc(ch,stdin);
			scanf("%d",&tmp);
			if(tmp==0) d[i][j]=INF;
			else d[i][j]=tmp;
			j++;
		}
		memset(vst,false,sizeof(vst));
		pos=0;
		prim(0);
		sort(bian,bian+pos,cmp);
		printf("Case %d:\n",++cases);
		for(i=0;i<pos;i++)
			printf("%c-%c %d\n",bian[i].st+'A',bian[i].ed+'A',bian[i].val);
	}
	return 0;
}

• Re:who can tell me where I am wrong???help!! thx!! (72) a024014 2007-08-25 16:45:22
  • 晕,原来用prim这题过不去... (104) a024014 2007-08-26 21:24:35
    • Re:晕,原来用prim这题过不去... (125) keky 2007-08-27 15:42:07
      • 我就是用prim过的 (17) qywyh_scut 2007-08-27 18:18:44
        • Re:我就是用prim过的 (28) a024014 2007-08-27 20:08:02