| ||||||||||
| 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 | |||||||||
求大牛看看我代码。。。为什么错了。。!!#include<iostream>
#include<cmath>
using namespace std;
double g[205][205];
int x[205],y[205];
int n;
typedef struct
{
int begin ,end;
int weight;
}edge;
edge mst[205];
void init()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
g[i][j]=fabs(double((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])));
}
}
}
int prim()
{
int i,j,min,vx,vy,weight,minweight;
edge edge1;
for(i=1;i<=n-1;i++)
{
mst[i].begin=1;
mst[i].end=i+1;
mst[i].weight=g[1][i+1];
}
for(i=1;i<=n-1;i++)//共需选出n-1条边
{
minweight=INT_MAX;
min =i;
for(j=i;j<=n-1;j++)
{
if(mst[j].weight<minweight)
{
minweight=mst[j].weight;
min=j;
}
}
if(mst[min].end==2) return mst[min].weight;
edge1=mst[i];
mst[i]=mst[min];
mst[min]=edge1;//将mst[i]加入最小生成树
vx=mst[i].end ;
for(j=i+1;j<=n-1;j++)
{
vy=mst[j].end;
weight=g[vx][vy];
if(weight<mst[j].weight)
{
mst[j].weight=weight;
mst[j].begin=vx;
}
}
}
}
int main()
{
int i,j;
int count=1;
while(cin>>n)
{
if(n==0) break;
for(i=1;i<=n;i++)
{
scanf("%d%d",&x[i],&y[i]);
}
init();
cout.precision(3);
cout<<fixed;
cout<<"Scenario #"<<count<<endl;
cout<<"Frog Distance = "<<sqrt(double(prim()))<<endl;
count++;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator