一道蛮基础的最小生成树的题
题意也没绕什么圈子
只是叙述的有点累赘而已（loj上是这样的
也就读入加建边需要稍稍稍多想一下下
对于我这么一个蒟蒻
这是一道很好的板子题
（洛谷和loj上有一点点小不同，主要按loj的题面）
--------------------------------------------------------------------------------
（今日份懒得整题面qwq）
--------------------------------------------------------------------------------
k个村庄装上卫星设备后
可以把这k个村庄看成一个点
（这不是缩点qwq）
那么只需要求（n-k+1）个点和（n-k）条边所构成的最小生成树
kruskal一下
最后一次操作室加入生成树的边权就是最终答案
--------------------------------------------------------------------------------
显然有可能排序后
kruskal到的边不止（n-k）条
但是我比较emm...
就wawawa喽
--------------------------------------------------------------------------------
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
inline int read()
{
int sum = 0,p = 1;
char ch = getchar();
while(ch < ‘0‘ || ch > ‘9‘)
{
if(ch == ‘-‘)
p = -1;
ch = getchar();
}
while(ch >= ‘0‘ && ch <= ‘9‘)
{
(sum *= 10) += ch - ‘0‘;
ch = getchar();
}
return sum * p;
}
int n,k,cnt,tot;
double ans;
int x[505],y[505],fa[505];
struct edge
{
int l,r;
double wei;
}e[500005];
double getdis(int x1,int y1,int x2,int y2)
{
return (double) sqrt((double)(x1 - x2)*(x1 - x2) + (double)(y1 - y2) * (y1 - y2));
}
int findfa(int o)
{
if(o == fa[o])
return o;
else
return fa[o] = findfa(fa[o]);
}
int cmp(edge a,edge b)
{
return a.wei < b.wei;
}
void kruskal()
{
int u,v,mrk = 0;
sort(e+1,e+cnt+1,cmp);
for(int i = 1;i <= cnt;i++)
{
u = findfa(e[i].l);
v = findfa(e[i].r);
if(u == v)
continue;
fa[u] = v;
mrk++;
if(mrk == n - k)
{
ans = e[i].wei;
break;
}
}
}
int main()
{
n = read(),k = read();
if(k >= n)
{
printf("0.00");
return 0;
}
if(k == 0)
k = 1;
for(int i = 1; i <= n; i++)
x[i] = read(),y[i] = read();
for(int i = 1; i <= n; i++)
for(int j = i + 1; j <= n; j++)
{
cnt++;
e[cnt].l = i;
e[cnt].r = j;
e[cnt].wei = getdis(x[i],y[i],x[j],y[j]);
}
for(int i = 1;i <= n;i++)
fa[i] = i;
kruskal();
printf("%.2lf",ans);
return 0;
}
Arctic Network（洛谷）--北极通讯网络（loj）
原文：https://www.cnblogs.com/darlingroot/p/10915080.html