题解 P1265 【公路修建】

牛瓜瓜 · 2020-08-01 12:52:48 · 题解

发现其他的题解都没有给出合理的证明说它为什么是最小生成树

~~否则它怎么难度标签会更模板题不一样~~

首先证明（1）的确实是符合最小生成树的

这里C代表了除了A，B剩下的节点，由题意可以知道圈1\le圈2,圈3那这三坨要想构成最小生成树，肯定是要选圈1和圈2，圈3中较小的一个，而不选圈2和圈3

我们来看看第二个

要想产生（2）这种情况，必定有圈1\le圈2,圈2\le圈3,圈3\le圈1那也就是三条边都是一样长的，那随便选两条都是可以的。

综上，这样才能看出它确实是最小生成树

代码难度比较低，就是一个模板

但是注意假如强行加n^2条边会MLE，其实我们不用存每条边，因为可以O(1)计算任意两点的距离

#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;

#define N 5103

template<class TT> inline void read(TT &xx)

{

   xx=0;char cc=getchar();bool ff=false;

   while(cc<'0'||cc>'9'){if(cc=='-')ff=true; cc=getchar();}

   while(cc>='0'&&cc<='9'){xx=(xx<<3)+(xx<<1)+cc-'0';cc=getchar();}

   if(ff) xx=-xx;

}

int x[N],y[N],n;

double dis[N],ans;

bool v[N];

#define d(i,j) sqrt((double)(x[i]-x[j])*(x[i]-x[j])+(double)(y[i]-y[j])*(y[i]-y[j]))

#define min(i,j) (i<j)?i:j

int main()

{

    freopen("road.in","r",stdin);

    read(n);

    for(int i=1;i<=n;i++) read(x[i]),read(y[i]),dis[i]=(double)100000008;

    dis[1]=0;

    for(int k=1;k<=n;k++)

    {

        double w=(double)100000008;

        int pos=666;//w记录最短距离，pos记录最近节点

        for(int j=1;j<=n;j++)

            if(!v[j] && w>dis[j])

                pos=j,w=dis[j];

        //printf("get- dis[%d]=%lf\n",pos,dis[pos]);

        v[pos]=true;

        ans+=dis[pos];

        for(int j=1;j<=n;j++)

            if(!v[j]) dis[j]=min(dis[j],d(pos,j));

    }

    printf("%.2lf\n",ans);

    return 0;

}