洛谷传送门

loj传送门

一道蛮基础的最小生成树的题

题意也没绕什么圈子

只是叙述的有点累赘而已(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 = ,p = ;
char ch = getchar();
while(ch < '' || ch > '')
{
if(ch == '-')
p = -;
ch = getchar();
}
while(ch >= '' && ch <= '')
{
(sum *= ) += ch - '';
ch = getchar();
}
return sum * p;
} int n,k,cnt,tot;
double ans;
int x[],y[],fa[]; struct edge
{
int l,r;
double wei;
}e[]; 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 = ;
sort(e+,e+cnt+,cmp);
for(int i = ;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 ;
}
if(k == )
k = ;
for(int i = ; i <= n; i++)
x[i] = read(),y[i] = read();
for(int i = ; i <= n; i++)
for(int j = i + ; 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 = ;i <= n;i++)
fa[i] = i;
kruskal();
printf("%.2lf",ans);
return ;
}

最新文章

  1. BZOJ 2946: [Poi2000]公共串
  2. AutoBundle in asp.net mvc 5
  3. php中的常用数组函数(五)(数组中获取键名集合)
  4. Jquery自定义图片上传插件
  5. DNS:www.flickr.com
  6. 周赛-Toy Cars 分类: 比赛 2015-08-08 15:41 5人阅读 评论(0) 收藏
  7. System.out.println调试输出
  8. 前端面试题和setTimeout异步
  9. 晨曦之光 linux Crontab 使用(转)
  10. POJ 2914 Minimum Cut 最小割图论
  11. static静态初始化块
  12. gameUnity 0.15 beta 网络游戏框架
  13. APUE学习心得
  14. 关于安卓百度地图SDK报错:Multiple dex files define Lcom/baidu/android/bbalbs/common/a/a;
  15. (十三)Batch Processing
  16. 动态修改JS对象的值及React setState
  17. Oracle 11gR2 客户端windows 10安装后PL/SQL配置
  18. gensim自然语言处理
  19. 深度解析 Vue 响应式原理
  20. 数据库之mysql练习

热门文章

  1. Mysql备份参数
  2. Mysql多实例数据库安装应用
  3. 数据库Dao层编增删改查写,数据库事务,数据库升级
  4. 【Python】time库
  5. python 自动化实现定时发送html报告到邮箱
  6. 第二篇,前端高性能JavaScript优化
  7. css div布局示例2(head-main-footer
  8. MySql5.6表操作
  9. CAN总线电平(隐性与显性)
  10. 题解【2.23考试T2】str