| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
wa的小弟要哭了!求大牛看看我的代码!全部注释了!已知的数据是全过了的!#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator