Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

wa的小弟要哭了!求大牛看看我的代码!全部注释了!已知的数据是全过了的!

Posted by andrew020 at 2010-07-22 17:51:22
#include <iostream>
#include <cmath>
using namespace std;

#define M 210
#define MaxLen 20000

int main()
{
	int n,i,j,k,v,cases,counter;
	int x[M],y[M];
	float G[M][M];
	float min,temp;
	int status[M],in[M];
	float FrogDistance;
	cases=1;
	while(cin>>n)
	{
		if(n==0)
			break;
		FrogDistance=0;
		//inPut
		for(i=1;i<=n;i++)//起点为1号,终点为2号,其他点从3起顺次编号
			cin>>x[i]>>y[i];
		//createG
		for(i=1;i<=n;i++)
			for(int j=i;j<=n;j++)
			{
				if(i==j)
					G[i][j]=MaxLen;
				else
					G[i][j]=sqrt((float)(x[i]-x[j])*(x[i]-x[j])+(float)(y[i]-y[j])*(y[i]-y[j]));
				G[j][i]=G[i][j];
			}
		memset(in,0,M);//初始化已连接点集合,全部为零。连接时从“1”位开始,连续填入被连接点的编号
		memset(status,0,M);//初始化状态脚标,1为被连接,0为未被连接。脚标标示点的编号
		status[1]=1;//默认起点被连接
		in[1]=1;//默认起点在已连接集合里,且为第一位
		counter=1;//被连接点的总数,默认为1
		//Prim
		while(status[2]==0/*当终点被连接上时,循环结束*/)
		{
			temp=0;
			min=(float)MaxLen;
			for(j=1;j<=counter;j++)
			{	
				for(k=1;k<=n;k++)
				{	
					if((G[in[j]][k]<min)&&(status[in[j]]==1)&&(status[k]==0))
					{
						min=G[in[j]][k];
						temp=G[in[j]][k];
						v=k;
					}
				}
			}
			counter=counter+1;//更新被连接点数
			status[v]=1;//更新状态
			in[counter]=v;//更新被连接点集合
			//更新结果
			if(FrogDistance<temp)
				FrogDistance=temp;
		}
		cout.setf(ios::fixed);
		cout.precision(3);
		cout<<"Scenario #"<<cases<<endl;
		cout<<"Frog Distance = "<<FrogDistance<<endl<<endl;
		cases++;
	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator