P1265 公路修建题解 » 老官童鞋gogo的博客

题目传送门

题解

题目理解与强调

这道题目翻译过来即为：一个图中有 $ n $ 个点，使用 $ n-1 $ 条边将这 $ n $ 个点连接起来，形成一棵树，在选用这 $ n-1 $条边时，要求每次每个点找到与它最近的点连接，直到所有节点连接到一起，其他的连边要求：

如果两个点申请相互连边，则让它们只连一条边；
~~如果三个或以上的点连成环。则三条边中最短的那一条将不允许连接；~~

思路分析

为什么将第二条要求删去了？假设三条边的长度为 $ a,b,c $ ，则根据之前的条件得出 $ a<b<c<a $ ，显然，这是不存在的。

所以这个问题可以转化为最小生成树。求最小生成树的常见的方法有两种，一种是Kruskal，另一种是Prim，这里使用Prim更好，如果使用Kruskal算法，那么要对所有的边的长度进行存储并排序，再稠密图中存储 $ 5000 $ 个点需要大量的空间，而使用Prim算法可以在过程中求出两点间的距离，节省空间。

首先将第一个点放入树中，从第一个点开始，不断更新节点与其他节点到树的距离，然后将树上每条边的长度相加即可。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 100000000
#define N 1000
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
struct Node
{
    ll x,y;
}a[500001];
bool vis[500001];
ll dis[500001];
double ans;
int main()
{
//    freopen("P1265_2.in.txt","r",stdin);
    int n=read();
    for(int i=1;i<=n;i++)
    {
        dis[i]=1e18;
    }
    dis[1]=0;
    for(int i=1;i<=n;i++)
    {
        a[i].x=read();
        a[i].y=read();
    }
    for(int i=1;i<n;i++)
    {
        int now=0;
        for(int j=1;j<=n;j++)
        {
            if(vis[j]==0&&(now==0||dis[now]>dis[j]))
            {
                now=j;
            }
        }
        vis[now]=1;
        for(int j=1;j<=n;j++)
        {
            if(vis[j]==0)
            {
                dis[j]=min(dis[j],(a[j].x-a[now].x)*(a[j].x-a[now].x)+(a[j].y-a[now].y)*(a[j].y-a[now].y));
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        ans+=sqrt((double)dis[i]);
    }
    printf("%.2lf",ans);
    return 0;
}