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

麻烦大牛看下,我的程序为什么CE呀?谢谢哈~

Posted by acm_pku at 2009-07-19 00:25:35
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;


struct A
{
	double x;
	double y;
};


struct T
{
	int begin;
	int end;
	double length;
};

const int maxn = 101;
const int maxn2 = 10001;
int parent[maxn];
int rank[maxn];
A input[maxn];
T line[maxn2];




bool cmp(T &a, T &b)
{
	return a.length < b.length;
}

double distance(A &a, A &b)
{
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

void init(int n)
{
	for(int i = 1; i <= n; i++)
	{
		parent[i] = i;
		rank[i] = 0;
	}

}


int find_set(int x)
{
	if(x != parent[x])
		parent[x] = find_set(parent[x]);
	return parent[x];
}

void unions(int a, int b)
{
	if(rank[a] > rank[b])
		parent[b] = a;
	else
	{
		parent[a] = b;
		if(rank[a] == rank[b])
			rank[b] ++;
	}
}

int main()
{
	int n, i, j;
    scanf("%d", &n);
	for(i = 1; i <= n; i++)
	{
		scanf("%lf%lf", &input[i].x, &input[i].y);
	}
	int k = 0;
	for(i = 1; i <= n; i++)
	{
		for(j = i + 1; j <= n; j++)
        {
			line[k].begin = i;
			line[k].end = j;
			line[k++].length = distance(input[i], input[j]);
		}
 
	}
	sort(line, line + k, cmp);
	double sum = 0;
	int num = 0;
	init(n);
    for(i = 0; i < k; i++)
	{
		int a1 = find_set(line[i].begin);
		int b1 = find_set(line[i].end);
		if(a1 != b1)
		{
			unions(a1, b1);
			sum += line[i].length;
			num ++;
		}
		if(num == n - 1)
			break;
	}
	printf("%.2lf\n", sum);
	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