| ||||||||||
| 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 | |||||||||
麻烦大牛看下,我的程序为什么CE呀?谢谢哈~#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator