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 hdjtdxacm at 2009-03-04 21:27:58 on Problem 3625
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct st
{
	int x;
	int y;
	double dis;
}edge[1010];
double x[1010],y[1010];
bool cmp(const st&a,const st&b)
{
	return a.dis < b.dis;
}

double Kruskal(int v,int e)
{
	int i,j,an1,an2;
	int set[1010];
	for(i = 1;i <= v;i++)
		set[i] = i;
	int count = 1;
	double sum = 0;
	sort(edge + 1,edge + e +1,cmp);
	i = 1;
	while(count < v)
	{
		an1 = set[edge[i].x];
		an2 = set[edge[i].y];
		if(an1 != an2)
		{
			count++;
			sum += edge[i].dis;
			for(j = 1;j <= v;j++)
				if(set[j] == an2)
					set[j] =an1;
		}
		i++;
	}
	return sum;
}
int main()
{
	int i,j,n,m,k,a,b,temp;
	scanf("%d%d",&n,&m);
	for(i = 1;i <= n;i++)
		scanf("%lf%lf",&x[i],&y[i]);
	k = 0;
	for(i = 1;i <n;i++)
		for(j = i+1;j <= n;j++)
		{
			edge[++k].x = i;
			edge[k].y = j;
			edge[k].dis = sqrt(double((y[j] - y[i])*(y[j] - y[i])) + double((x[j] - x[i])*(x[j] - x[i])));
		}
	for(i = 1;i <= m;i++)
	{
		scanf("%d%d",&a,&b);
		if(a > b){temp = a;a = b; b = temp;}
		for(j = 1;j <= k;j++)
		{
			if(edge[j].x == a&&edge[j].y == b)
				edge[j].dis = 0;
		}
	}
	printf("%.2lf\n",Kruskal(n,k));
	return 0;
}
/*Sample Input

4 1
1 1
3 1
2 3
4 3
1 4
Sample Output

4.00
*/

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