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

秒速五厘米 2023-05-28 11:12 18阅读 0赞

### 文章目录 ###

*  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][https_blog.csdn.net_qq_45034708]  
> *如果文章对你有帮助，记得关注点赞收藏❤*

[https_blog.csdn.net_qq_45034708]: https://blog.csdn.net/qq_45034708