首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >最小生成树-Magicpig密室出逃(Kruskal+并查集)

最小生成树-Magicpig密室出逃(Kruskal+并查集)

作者头像
唔仄lo咚锵
发布2020-09-15 11:25:06
3090
发布2020-09-15 11:25:06
举报

文章目录

  • Kruskal算法
  • 题目
    • 分析
    • 代码
  • 小结

Kruskal算法


Kruskal算法是按边权从小到大依次加入边,如果某次加边产生了环(并查集判断),就扔掉这条边,直到加入了n-1条边,即形成了一棵树。

题目


在金字塔中有一个叫Room-of-No-Return 的大房间,非常不幸的是Magicpig现在被困在这个房间里。房间的地板上有一些钩子。在房间的墙上有一些古老的埃及文字:“如果你想逃离这里,你必须用绳索连接所有这些钩子,然后一个秘密的门将打开,你将获得自由。如果你不能这样做,你将永远被困在这里”。幸运的是Magicpig有一条长度为L的绳索,他可以把它切成段,每段可以连接两个钩子,如果他能用这段绳子连接所有钩子,并且连接的绳子不能出现环路,就可以成功逃脱!Kinfkong想知道他是否可以逃跑。

输入格式:

输入包含一个或多个数据集。在每个输入数据集的第1行有两个整数n和L,其中n是钩子的数量,L是绳索的长度。接下来的n行包含钩子的一系列坐标,每个坐标是一个非负整数对,并且每个整数小于32768,每对都用空格分隔(2<=n<=100,L<=32767)。钩子的数量n 为零表示输入结束。

输出格式:

对于每个数据集,如果Magicpig可以逃脱,打印一个字符串”Success!”,否则打印“Poor magicpig!”.

输入样例:

2 1
0 0
1 1 
2 2
0 0
1 1
0

输出样例:

Poor magicpig!
Success!

分析

首先准备工作把题目读入的坐标,构建成完全连通图,得到边(两点距离公式)。 然后就是套用Krusakal算法,先对边排序,遍历每次选最小的边,然后用并查集判断它的两个端点是否在一个集合,不是的话则加入该边,更新花费和并操作。 最后返回花费和绳索长度比较即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define maxn 102
int n, m;
int cnt;//边数
int root[maxn];
struct node {
	int x, y;//坐标
	int idx;//下标
}points[maxn];
struct node2 {
	int u, v;//端点
	double cost;//权值
}edge[maxn*maxn];
bool cmp(node2 a, node2 b) {
	return a.cost < b.cost;
}
int Find(int x) {
	return root[x] == x ? x : root[x] = Find(root[x]);
}
double Kruskal() {
	for (int i = 0; i <= n; i++)
		root[i] = i;
	sort(edge + 1, edge + cnt, cmp);
	double ans = 0;
	for (int i = 1; i <= cnt; i++) {
		int u = Find(edge[i].u);
		int v = Find(edge[i].v);
		if (u != v) {
			root[u] = v;//Union
			ans += edge[i].cost;
		}
	}
	//判断非连通图
	return ans;
}
int main() {
	while (~scanf("%d", &n) && n != 0) {
		scanf("%d", &m);
		for (int i = 1; i <= n; i++) {
			scanf("%d%d", &points[i].x, &points[i].y);
			points[i].idx = i;
		}
		cnt = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {
				edge[cnt].u = points[i].idx;
				edge[cnt].v = points[j].idx;
				double cost = pow(points[i].x - points[j].x, 2);
				cost += pow(points[i].y - points[j].y, 2);
				cost = sqrt(cost);
				edge[cnt].cost = cost;
				cnt++;
			}
		}
		double ans = Kruskal();
		if (ans > m)printf("Poor magicpig!\n");
		else printf("Success!\n");
	}
	return 0;
}

小结


  1. 一般Kruskal算法最后还要判断构建出来的图是否为连通图,由于本题把坐标两两求边得到完全连通图便省略。
  2. 图的存储问题:若邻接矩阵超限,考虑邻接表(vector实现)。

原创不易,请勿转载本不富裕的访问量雪上加霜 ) 博主首页:https://blog.csdn.net/qq_45034708

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-03-25 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 文章目录
  • Kruskal算法
  • 题目
    • 分析
      • 代码
      • 小结
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档