ShineEternal的小书屋

ShineEternal的小书屋

https://blog.csdn.net/kkkksc03

题解 P2872 【[USACO07DEC]道路建设Building Roads】

posted on 2019-10-21 19:58:30 | under 题解 |

$My\ blog$

description:

在一个准备连边的图中已经连好一些边,问使图联通所需的最小价值。

solution:

这道题和正常的最小生成树一样,只不过已经给出了一些边了。

但是如果直接把两个点连起来不怎么方便,怎么办呢?

突然发现了一个比较好的方法:

把已经给出的边权值算做0就行了

涨姿势了

个人认为代码写的不算太乱(虽然我是大括号换行的,值得一看)

code:

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct ben
{
    int x,y;
    double val;
}a[1000005];
int cmp(const ben &a,const ben &b)
{
    return a.val<b.val;
}
int fa[5005];
int find(int x)
{
    if(fa[x]!=x)return fa[x]=find(fa[x]);
    return fa[x];
}
double sqr(double ww)
{
    return ww*ww;
}
double x[1005],y[1005];
double d(int i,int j)
{
    return sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
}
int main()
{
    int n,m,cnt=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&x[i],&y[i]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            double tmp=d(i,j);
            a[++cnt].x=i;
            a[cnt].y=j;
            a[cnt].val=tmp;
        }
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[++cnt].x=x;
        a[cnt].y=y;
        a[cnt].val=0;
    }
    sort(a+1,a+cnt+1,cmp);
    double ans=0;
    int k=0;
    for(int i=1;i<=cnt;i++)
    {
        int x=find(a[i].x);
        int y=find(a[i].y);
        if(x!=y)
        {
            fa[y]=x;
            ans+=a[i].val;
            k++;
        }
        if(k==n-1)break;
    }
    printf("%.2lf\n",ans);
    return 0;
}