描述
http://www.lydsy.com/JudgeOnline/problem.php?id=1626
给出\(n\)个点的坐标,其中一些点已经连通,现在要把所有点连通,求修路的最小长度.
分析
已经连好一些边的最小生成树问题.
这里顺带复习了一下Prim和Krusakal.
Prim的证明:
设当前已经连好的树为\(T\),当前最小的边为\(e\),我们来证明\(e\)一定在最小生成树\(G\)中.
假设\(e\)不在\(G\)中,则连通\(G-T\)和\(T\)的边\(e'\)一定比\(e\)大(或相等).此时我们在\(G\)中加入\(e\),会形成环,去掉环中的\(e'\),树依然连通,而花费更小了,这与\(G\)是最小生成树矛盾.(如果\(e\)与\(e'\)相等那么虽然花费不会更小,也就是说\(e\)可以不再\(G\)中,但是我们也可以用\(e\)替换\(e'\),换言之,\(e\)在\(G\)中是不错误的.)
所以\(e\)一定在最小生成树\(G\)中.
Kruskal的证明:
设当前连接两个不连通分量的最小的边为\(e\),我们来证明\(e\)一定在最小生成树\(G\)中.
假设\(e\)不再\(G\)中,则连通这两个分量的边\(e'\)一定比\(e\)大(或相等).此时我们 在\(G\)中加入\(e\),会形成环,去掉环中的\(e'\),树依然连通,而花费更小了,这与\(G\)是最小生成树矛盾.(如果\(e\)与 \(e'\)相等那么虽然花费不会更小,也就是说\(e\)可以不再\(G\)中,但是我们也可以用\(e\)替换\(e'\),换言之,\(e\)在 \(G\)中是不错误的.)
#include <bits/stdc++.h>
using namespace std; const int maxn=+;
struct pt{
double x,y;
pt(double x=,double y=):x(x),y(y){}
}p[maxn];
struct edge{
int from,to;
double d;
edge(){}
edge(int from,int to,double d):from(from),to(to),d(d){}
bool operator < (const edge &rhs) const { return d<rhs.d; }
}g[maxn*maxn];
int n,m,cnt=;
int f[maxn];
double ans;
inline double dis(pt a,pt b){ return sqrt(pow(a.x-b.x,)+pow(a.y-b.y,)); }
inline int find(int x){ return x==f[x]?x:f[x]=find(f[x]); }
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
f[i]=i;
}
for(int i=;i<=m;i++){
int u,v; scanf("%d%d",&u,&v);
int fu=find(u),fv=find(v);
if(fu!=fv) f[fu]=fv,cnt++;
}
for(int i=;i<=n;i++)for(int j=;j<=n;j++) g[(i-)*n+j]=edge(i,j,dis(p[i],p[j]));
sort(g+,g++n*n);
int tot=n*n;
for(int i=;i<=tot,cnt<=n;i++){
int fx=find(g[i].from),fy=find(g[i].to);
if(fx!=fy){
f[fx]=fy;
ans+=dis(p[g[i].from],p[g[i].to]);
cnt++;
}
}
printf("%.2lf\n",ans);
return ;
}