ACM/ICPC 之 Kruskal范例(POJ1128(ZOJ1083))

  最小生成树范例,Kruskal解法-以边为主体扩展最小生成树,需要利用并查集



ZOJ1203-Swordfish

  

  题意:求n个给定平面坐标的城市中的一条平面距离上的最短路长(保留两位小数)

  题解:这道题数据不是很大,用Kruskal和Prim等算法都能够做。

     Kruskal的算法思路是以边为主体扩展结点,即先选取权值最少的边,将两个不连通的端点加入到同一集合中(使其连通),舍去该边,接着找权值次小的,以此类推...

     如果两个端点连通,则直接舍去该边。

     因此可以先将所有边依据权值大小排序后,然后依次查找即可,为了较快地表示两个端点连通(属于同一集合),需要用到并查集的路径压缩。

 1 //剑鱼行动-Kruskal
 2 //找出n个给定平面坐标的城市中的一条最短路长(保留两位小数)
 3 //Time:0Ms    Memory:432K
 4 #include<iostream>
 5 #include<cstring>
 6 #include<cstdio>
 7 #include<cmath>
 8 #include<algorithm>
 9 using namespace std;
10
11 #define MAX    101
12 #define POW2(x) ((x)*(x))
13
14 struct City {
15     double x, y;
16 }c[MAX];
17
18 struct Edge {
19     int u, v;    //端点
20     double road;
21     friend bool operator < (Edge e1, Edge e2) { return e1.road < e2.road; }
22 }e[MAX*MAX];
23
24 int n, m;
25 int fa[MAX];
26 double minroad;
27
28 int Find(int x)
29 {
30     return fa[x] < 0? x : fa[x] = Find(fa[x]);    //查根+路径压缩
31 }
32
33 //加权法则合并
34 void Union(int r1,int r2)
35 {
36     int num = fa[r1] + fa[r2];    //集合元素总数-以负数计数
37     if (fa[r1] > fa[r2])    //r2集合元素多
38     {
39         fa[r1] = r2;
40         fa[r2] = num;
41     }
42     else {    //r1集合元素多
43         fa[r2] = r1;
44         fa[r1] = num;
45     }
46 }
47
48 void kruskal()
49 {
50     minroad = 0;
51     memset(fa, -1, sizeof(fa));
52     int num = 0;    //已用结点数
53     for (int i = 0; i < m; i++)
54     {
55         int r1 = Find(e[i].u);
56         int r2 = Find(e[i].v);
57         if (r1 == r2)    continue;
58         minroad += e[i].road;
59         Union(r1, r2);
60         num++;
61         if (num == n - 1) break;
62     }
63 }
64
65 int main()
66 {
67     int cas = 0;
68     while (scanf("%d", &n), n)
69     {
70         for (int i = 0; i < n; i++)
71             scanf("%lf%lf", &c[i].x, &c[i].y);
72
73         m = 0;
74         for (int i = 0; i < n; i++)
75             for (int j = i + 1; j < n; j++)
76             {
77                 double d = sqrt(POW2(c[i].x - c[j].x) + POW2(c[i].y - c[j].y));
78                 e[m].road = d;
79                 e[m].u = i;
80                 e[m++].v = j;
81             }
82
83         sort(e, e + m);
84
85         kruskal();
86         if (cas)    printf("\n");    //博主在此PE过= =
87         printf("Case #%d:\n", ++cas);
88         printf("The minimal distance is: %.2lf\n", minroad);
89     }
90
91
92     return 0;
93 }
时间: 04-05

ACM/ICPC 之 Kruskal范例(POJ1128(ZOJ1083))的相关文章

ACM/ICPC 之 Prim范例(ZOJ1586-POJ1789(ZOJ2158))

两道Prim解法范例题型,简单的裸Prim,且两题相较以边为重心的Kruskal解法而言更适合以点为重心扩展的Prim解法. ZOJ1586-QS Network 题意:见Code 题解:直接的MST题型,本题的图为稠密图,因此适合以点为扩展导向的Prim算法(代码量也较少). 大抵是先以某点A为中心,标记点A,访问其邻接点,更新全图到该点的距离(不通路以INF表示),找出最短距离的点B 标记最短距离的B点,然后访问其邻接点,更新邻接点到B点的最短距离,找出最短距离的点C...以此类推... 将

ACM/ICPC 之 SPFA范例两道(POJ3268-POJ3259)

两道以SPFA算法求解的最短路问题,比较水,第二题需要掌握如何判断负权值回路. POJ3268-Silver Cow Party //计算正逆最短路径之和的最大值 //Time:32Ms Memory:360K #include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<algorithm> using namespace std; #define

ACM/ICPC 之 BFS范例(ZOJ2913)

通过一道经典BFS例题阐述BFS思路 ZOJ2913-Bus Pass 题意:找一个center区域,使得center到所有公交线路最短,有等距的center则输出id最小的. 题解:经典的BFS,由公交线路最多只经过10*20个区域,而总区域数可达10^5个,因此应该从公交线路通过队列一层层向外扩展,最后判断一次center的位置即可. 1 //选定一个center使得其到所有公交线路最短 2 //对所有公交线路进行BFS(公交线路比其他区域少得多) 3 //Time:150Ms Memory

ACM/ICPC 之 拓扑排序+DFS(POJ1128(ZOJ1083))

经典的拓扑排序问题,难点在于字典序输出和建立拓扑图,另外理解题意是最难的难点,没有之一... POJ1128(ZOJ1083)-Frame Stacking 题意:每个图片由同一字母组成的边框表示,每个图片的字母都不同: 在一个最多30*30的区域放置这些图片,问底层向顶层叠加的图片次序,多选时按字典序输出 注:每个图片的四边都会有字符显示,其中顶点显示两边. 题解:题意的理解是难点,题目对图片的范围确定说得有点含糊不清,博主一开始就被出现的五张图片的样例迷惑,理解重心放错了.题目最需要理解的是

《ACM/ICPC 算法训练教程》读书笔记一之数据结构(堆)

书籍简评:<ACM/ICPC 算法训练教程>这本书是余立功主编的,代码来自南京理工大学ACM集训队代码库,所以小编看过之后发现确实很实用,适合集训的时候刷题啊~~,当时是听了集训队final的意见买的,感觉还是不错滴. 相对于其他ACM书籍来说,当然如书名所言,这是一本算法训练书,有着大量的算法实战题目和代码,尽管小编还是发现了些许错误= =,有部分注释的语序习惯也有点不太合我的胃口.实战题目较多是比较水的题,但也正因此才能帮助不少新手入门,个人认为还是一本不错的算法书,当然自学还是需要下不少

2014 ACM/ICPC Asia Regional Guangzhou Online Wang Xifeng&#39;s Little Plot HDU5024

一道好枚举+模拟题目.转换思维视角 这道题是我做的,规模不大N<=100,以为正常DFS搜索,于是傻乎乎的写了起来.各种条件限制模拟过程 但仔细一分析发现对每个点进行全部八个方向的遍历100X100X100^8 .100X100个点,每个点在走的时候8中选择,TLE 于是改为另一个角度: 以符合要求的点为拐弯点,朝两个垂直的方向走,求出最远的距离.这样只要对每个点各个方向的长度知道,组合一下对应的就OK. 避免了每个点深搜. PS:搜索的时候x,y写反了,导致构图出现问题,以后用[dy][dx]

HDU 5014 Number Sequence(2014 ACM/ICPC Asia Regional Xi&#39;an Online) 题解

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5014 Number Sequence Problem Description There is a special number sequence which has n+1 integers. For each number in sequence, we have two rules: ● ai ∈ [0,n] ● ai ≠ aj( i ≠ j ) For sequence a and sequ

hdu6206 Apple 2017 ACM/ICPC Asia Regional Qingdao Online

地址:http://acm.split.hdu.edu.cn/showproblem.php?pid=6206 题目: Apple Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 530    Accepted Submission(s): 172 Problem Description Apple is Taotao's favouri

ACM ICPC 2008–2009 NEERC MSC A, B, C, G, L

这套题是我上周日, 就是前天打得一场组队赛, 题目不太好找 题目链接:http://codeforces.com/gym/100861 在virtual judge 上也可以提交哦! A ACM ICPC Rules: 题目大意: 有很多所高校参加预选赛, 并在预选赛取得了排名, 但是对于每所学校, 除了MSU有4个名额之外其他大学只有两个名额( 也就是说, 只有每个大学的前2名进决赛(MSU前四名)&& 最多有10个队伍进入决赛), 高中队伍不能进入决赛. 给出预选赛的排名, 输出可以进