jungle road.cpp

一个求最小生成树的acm题

#include <iostream.h>
#include <fstream.h>
int matrix[27][27];
int lowcost[27];
int nearvex[27];
int tree[27][3];
int number,input_int;
char input_char;                                                                                                                                                                                                                                                                                                   
void main()
{
	fstream infile;
	fstream outfile;
	infile.open("d:\\input.dat",ios::in);
	outfile.open("d:\\output.dat",ios::out);
	infile>>input_int;
	while(input_int!=0)
	{
		for(int i=0;i<=26;i++)
		{
			lowcost[i]=0;
			nearvex[i]=0;
			for(int j=0;j<=26;j++)
			{
				if(i==j){matrix[i][j]=0;}
				else{matrix[i][j]=10000;}
			}
		}
		number=input_int;
		for(i=0;i<number-1;i++)
		{
		    infile>>input_char>>input_int;
			int x=input_char-'A';
			int loop=input_int;
			for(int j=0;j<loop;j++)
			{
				infile>>input_char>>input_int;
				int y=input_char-'A';
				int cost=input_int;
				matrix[x][y]=cost;
				matrix[y][x]=cost;
			}
		}


	    for(i=1;i<number;i++)
		{
			lowcost[i]=matrix[0][i];nearvex[i]=0;
		}
		nearvex[0]=-1;int top=0;
		//tree[top][0]=nearvex[0];
		//tree[top][1]=0;
		//tree[top][2]=0;
		for(i=1;i<number;i++)
		{
			int mix=10000;int v=0;
			for(int j=0;j<number;j++)
			{
				if((nearvex[j]!=-1)&&(lowcost[j]<mix)){v=j;mix=lowcost[j];}
			}
			if(v)
			{
				tree[top][0]=nearvex[v];
				tree[top][1]=v;
				tree[top][2]=lowcost[v];
                nearvex[v]=-1;
				for(j=1;j<number;j++)
				{
					if(nearvex[j]!=-1&&matrix[v][j]<lowcost[j])
					{lowcost[j]=matrix[v][j];nearvex[j]=v;}
				}
			}
		}
		int total=0;
		for(i=0;i<number;i++)
		{total=total+lowcost[i];}
		outfile<<total<<'\n';
		infile>>input_int;
	}
}