博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[Aizu2224] Save your cats
阅读量:6267 次
发布时间:2019-06-22

本文共 1563 字,大约阅读时间需要 5 分钟。

 

题意:女(gua)巫(fu)建立了N个魔法桩,魔法桩之间连了M条魔法栅栏,形成了一个个封闭图形,困住了小(na)猫(er)们,你要砍掉一些魔法栅栏,使得小猫们能顺利逃脱

题解:

最大生成树

当图形形成一棵树时,才恰好不是封闭图形

构出最大生成树,未加入树的边的和即为答案

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #define ll long long 8 using namespace std; 9 10 const int N = 10010;11 12 int n,m,k,fa[N];13 bool vis[N*100];14 double ans;15 16 int find(int x) {17 return x==fa[x]?x:fa[x]=find(fa[x]);18 }19 20 struct Node { double x,y;}p[N];21 struct Edge {22 int x,y; double z;23 bool operator < (const Edge &a) const {24 return z>a.z;25 }26 }e[N*100];27 28 int gi() {29 int x=0,o=1; char ch=getchar();30 while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();31 if(ch=='-') o=-1,ch=getchar();32 while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();33 return o*x;34 }35 36 double cal(int i, int j) {37 return sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));38 }39 40 int main() {41 n=gi(),m=gi();42 for(int i=1; i<=n; i++) {43 scanf("%lf%lf", &p[i].x, &p[i].y); 44 } 45 for(int i=1; i<=m; i++) {46 int x=gi(),y=gi();47 double dis=cal(x,y);48 e[i]=(Edge){x,y,dis};49 }50 sort(e+1,e+m+1);51 for(int i=1; i<=n; i++) fa[i]=i;52 for(int i=1; i<=m; i++) {53 int x=e[i].x,y=e[i].y,xx,yy;54 xx=find(x),yy=find(y);55 if(xx==yy) continue; 56 fa[yy]=xx;57 vis[i]=1,k++;58 if(k==n-1) break;59 }60 for(int i=1; i<=m; i++) {61 if(!vis[i]) ans+=e[i].z;62 } 63 printf("%.3f", ans);64 return 0;65 }

 

转载于:https://www.cnblogs.com/HLXZZ/p/7571459.html

你可能感兴趣的文章
Cocos2D-x设计模式发掘之中的一个:单例模式
查看>>
很强大的HTML+CSS+JS面试题(附带答案)
查看>>
用树莓派实现RGB LED的颜色控制——C语言版本号
查看>>
VC2012编译CEF3-转
查看>>
java 自己定义异常,记录日志简单说明!留着以后真接复制
查看>>
Android 使用AIDL实现进程间的通信
查看>>
机器学习(Machine Learning)&深度学习(Deep Learning)资料
查看>>
jquery的图片轮播 模板类型
查看>>
C# 获取文件名及扩展名
查看>>
Web安全学习计划
查看>>
输出有序数组的连续序列范围
查看>>
zinnia项目功能分析
查看>>
windows cmd for paramiko
查看>>
SQL经典面试题集锦
查看>>
View学习(一)-DecorView,measureSpec与LayoutParams
查看>>
色彩力量!21款你应该知道的优秀品牌设计
查看>>
SDUT 3503 有两个正整数,求N!的K进制的位数
查看>>
【.Net】C# 根据绝对路径获取 带后缀文件名、后缀名、文件名、不带文件名的文件路径...
查看>>
Redis常用命令速查 <第二篇>
查看>>
CSS规范
查看>>