| ||||||||||
| 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<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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator