【BZOJ1626】[Usaco2007 Dec]Building Roads 修建道路

2014-06-12
竞赛题解 / 图论
BZOJUSACO最小生成树

描述 Description

Farmer John 最近得到了一些新的农场，他想新修一些道路使得他的所有农场可以经过原有的或是新修的道路互达（也就是说，从任一个农场都可以经过一些首尾相连道路到达剩下的所有农场）。有些农场之间原本就有道路相连。 所有 N(1 <= N <= 1,000)个农场（用 1..N 顺次编号）在地图上都表示为坐标为 (X_i, Y_i) 的点 (0 <= X_i <= 1,000,000；0 <= Y_i <= 1,000,000)，两个农场间道路的长度自然就是代表它们的点之间的距离。现在 Farmer John 也告诉了你农场间原有的 M(1 <= M <= 1,000) 条路分别连接了哪两个农场，他希望你计算一下，为了使得所有农场连通，他所需建造道路的最小总长是多少。

输入格式 InputFormat

第 1 行: 2 个用空格隔开的整数：N 和 M

第 2..N+1 行: 第 i+1 行为 2 个用空格隔开的整数：X_i、Y_i * 第 N+2..N+M+2 行: 每行用 2 个以空格隔开的整数 i、j 描述了一条已有的道路， 这条道路连接了农场 i 和农场 j.

输出格式 OutputFormat

第 1 行: 输出使所有农场连通所需建设道路的最小总长，保留 2 位小数，不必做 任何额外的取整操作。为了避免精度误差，计算农场间距离及答案时 请使用 64 位实型变量

样例输入 SampleInput

15 3
5 1
1 1
9 17
5 2
1 9
9 5
1 14
13 11
1 11
5 14
15 9
11 17
9 9
11 1
18 4
9 15
1 2
5 4

样例输出 SampleOutput

37.77

来源 Source

Silver

BZOJ 1626

代码 Code

MST. 求解怎么用 printf 输出 long double。。。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
struct point
{
    int z,y,x,fa;
}a[1005];
struct road
{
    int x,y;
    long double dis;
}b[2000005];
int i,j,t,n,m,l,r,k;
long double ans;
int getfa(int s)
{
    if (a[s].fa==s) return s;
    a[s].fa=getfa(a[s].fa);
    return a[s].fa;
}
long double getdis(int l,int r)
{
    long double tx=(long double)a[l].x-a[r].x,ty=(long double)a[l].y-a[r].y;
    return (sqrt(tx*tx+ty*ty));
}
bool comp(road a,road b)
{
    return a.dis<b.dis;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
    for (i=1;i<=n;i++)
    {
        a[i].fa=i;
    }
    for (i=1;i<=m;i++)
    {
        scanf("%d%d",&l,&r);
        if (getfa(l)!=getfa(r)) a[getfa(l)].fa=r;
    }
    t=0;
    for (i=1;i<=n;i++)
    {
        for (j=i;j<=n;j++) 
        {
            b[++t].x=i;b[t].y=j;b[t].dis=getdis(i,j);
        }
    }
    sort(b+1,b+t+1,comp);
    ans=0.0;
    for (i=1;i<=t;i++)
    {
        if (getfa(b[i].x)!=getfa(b[i].y))
        {
            ans+=b[i].dis;
            a[getfa(b[i].x)].fa=b[i].y;
        }
    }
    printf("%.2lf",(double)ans);
    //cout<<fixed<<setprecision(2)<<ans<<endl;
    return 0;
}