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

求大牛看看我代码。。。为什么错了。。!!

Posted by pyjacm at 2010-07-17 21:21:33 on Problem 2253
#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:
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