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;
}
原创不易,请勿转载(
本不富裕的访问量雪上加霜) 博主首页:https://blog.csdn.net/qq_45034708