ZOJ 1203 Swordfish 旗鱼 最小生成树,Kruskal算法
算法 生成 最小 zoj kruskal
2023-09-27 14:27:02 时间
A world beneath what we call cyberspace.
A world protected by firewalls,
passwords and the most advanced
security systems.
In this world we hide
our deepest secrets,
our most incriminating information,
and of course, a shole lot of money.
This is the world of Swordfish.
You who has watched the movie know that Gabriel at last got the money by threatening to hang Ginger to death. Why not Gabriel go get the money himself? Because these money keep jumping, and these accounts are scattered in different cities. In order to gather up these money Gabriel would need to build money transfering tunnels to connect all these cities. Surely it will be really expensive to construct such a transfering tunnel, so Gabriel wants to find out the minimal total length of the tunnel required to connect all these cites. Now he asks you to write a computer program to find out the minimal length. Since Gabriel will get caught at the end of it anyway, so you can go ahead and write the program without feeling guilty about helping a criminal.
Input:
The input contains several test cases. Each test case begins with a line contains only one integer N (0 <= N <=100), which indicates the number of cities you have to connect. The next N lines each contains two real numbers X and Y(-10000 <= X,Y <= 10000), which are the citie's Cartesian coordinates (to make the problem simple, we can assume that we live in a flat world). The input is terminated by a case with N=0 and you must not print any output for this case.
Output:
You need to help Gabriel calculate the minimal length of tunnel needed to connect all these cites. You can saftly assume that such a tunnel can be built directly from one city to another. For each of the input cases, the output shall consist of two lines: the first line contains "Case #n:", where n is the case number (starting from 1); and the next line contains "The minimal distance is: d", where d is the minimal distance, rounded to 2 decimal places. Output a blank line between two test cases.
Sample Input:
5 0 0 0 1 1 1 1 0 0.5 0.5 0
Sample Output:
Case #1: The minimal distance is: 2.83
分析:最小生成树,Kruskal问题求解。注意两个城市之间都有一条边相连。还有每两组输出之间空一行。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <cstdlib> using namespace std; #define maxn 5055 double ans; int cnt; int parent[110]; struct edge { int u, v; double w; }EG[maxn]; bool cmp(edge a, edge b) { return a.w < b.w; } int cmp2(const void *a, const void *b) { edge aa = *(const edge*)a; edge bb = *(const edge*)b; if(aa.w > bb.w) return 1; return -1; } int Find(int x) { if(parent[x] == -1) return x; return Find(parent[x]); } void Kruskal() { memset(parent, -1, sizeof(parent)); sort(EG, EG+cnt, cmp); //qsort(EG, cnt, sizeof(EG[0]), cmp2); ans = 0; for(int i = 0; i < cnt; i++) { int t1 = Find(EG[i].u), t2 = Find(EG[i].v); if(t1 != t2) { ans += EG[i].w; parent[t1] = t2; } } } int main() { int n, cas = 0; double x[110], y[110]; while(scanf("%d", &n), n) { for(int i = 0; i < n; i++) scanf("%lf%lf", &x[i], &y[i]); cnt = 0; for(int i = 0; i < n; i++) for(int j = i+1; j < n; j++) { EG[cnt].u = i; EG[cnt].v = j; EG[cnt].w = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); cnt++; } Kruskal(); if(cas > 0) printf("\n"); printf("Case #%d:\nThe minimal distance is: %.2f\n", ++cas, ans); //++cas; } return 0; }
版权声明:本文博主原创文章,博客,未经同意不得转载。
相关文章
- 算法 - 计数排序(Counting_Sort)
- 国密算法SM2 的JAVA实现(基于BC实现)
- GNN-静态表征-随机游走-2014:DeepWalk【步骤:①随机游走策略生成每个节点的训练序列(DFS),得到训练数据集;②套用Word2vec算法得到节点表示】【捕获二阶相似度】【浅层、同质图】
- 图算法(七):带一般过滤条件最短路径(Filtered Shortest Path)【适用场景:用于路径设计、网络规划等,通过对点边条件的过滤,控制最短路径的生成】【寻找两点间满足过滤条件的最短路径】
- 分布式 ID 生成算法 — SnowFlake
- 生成主键ID,唯一键id,分布式ID生成器雪花算法代码实现
- 最小生成树之Prim算法和Kruskal算法
- 【算法】Java-Redis-Hash算法对比-参考资料
- 机器学习算法中随机数的生成
- LeetCode_递归_回溯算法_中等_22.括号生成
- 一文搞懂RSA算法原理及简单实现
- Java实现Prim最小生成树算法
- 数据结构与算法之最好学的最小生成树
- Hibernate中UUID的生成算法
- 图论总结 最短路、最小生成树、二分图算法选择
- AcWing 858. Prim算法求最小生成树
- 唯一ID生成算法剖析(转)
- 算法 | 多种解题思路
- 最小生成树------Kruskal算法
- 年轻带Young GC算法示意图