#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
#define N 27
#define MAX_INT 20000000
using namespace std;
struct eg{
char x;
char y;
int w;
};
struct eg edge[75];
char parent[N]; /* MF Set, 树根的parent为负数,其绝对值表示这棵树的高度 */
int n, m;
/* 找i的根节点 */
int find(int i)
{
for(; parent[i] >= 0; i = parent[i]) ;
return i;
}
void merge(int x,int y, int px, int py)
{
if (px == py) return;
debug("%d的树根为%d,树高=%d,%d的树根为%d, 树高=%d\n", x, px, -parent[px], y, py, -parent[py]);
if (parent[px] < parent[py]) { /* x所在的树比y所在的树要高 */
parent[py] = px;
debug("合并后树根为%d, 高度=%d\n", px, -parent[px]);
}
else if (parent[px] > parent[py]) { /* x所在的树比y所在的树要矮 */
parent[px] = py;
debug("合并后树根为%d, 高度=%d\n", py, -parent[py]);
}
else {
parent[py] = px;
parent[px]--; /* 树的高度加1 */
debug("合并后树根为%d, 高度=%d\n", px, -parent[px]);
}
}
static int
compare(const void *p1, const void *p2)
{
return ((struct eg *)p1)->w - ((struct eg *)p2)->w;
}
int kruskal()
{
int i, total_cost;
int px, py;
total_cost = 0;
qsort(edge, m, sizeof(eg), compare); /* 按边的长度从小到大排序 */
memset(parent, -1, sizeof(parent));
for (i = 0; i < m; i++) {
debug("%c-%c : %d\n", edge[i].x+'A', edge[i].y + 'A', edge[i].w);
}
for (i = 0; i < m; i++) {
px = find(edge[i].x);
py = find(edge[i].y);
if (px != py) { /* 这条边的两个顶点不在同一个集合中 */
merge(edge[i].x, edge[i].y, px, py);
debug("边%c-%c加入集合, 长度为%d\n", edge[i].x+'A', edge[i].y+'A', edge[i].w);
total_cost += edge[i].w;
}
}
return total_cost;
}
int main()
{
int i, j, w;
char ch;
char adj;
while (cin >> n && n) {
m = 0;
for (i = 1; i < n; i++) {
cin >> ch >> j;
while (j--) {
cin >> adj >> w;
edge[m].x = ch-'A';
edge[m].y = adj-'A';
edge[m].w = w;
m++;
}
}
debug("总共有%d条边\n", m);
printf("%d\n", kruskal());
}
return 0;
}
分享到:
相关推荐
NULL 博文链接:https://200830740306.iteye.com/blog/603493
NULL 博文链接:https://128kj.iteye.com/blog/1705139
NULL 博文链接:https://128kj.iteye.com/blog/1707218
jungle.in为输入数据,jungle.out为输出数据
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
NULL 博文链接:https://128kj.iteye.com/blog/1704752
poj1087贪心算法实验报告 poj1087贪心算法实验报告
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
POJ各题算法分类和题目推荐.pdf
供初学编程基本算法的人练习使用,在poj.grids.cn上
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
最小度限制生成树的求法也不是很难,先把度被限制的那个点(s点)去掉,求一次MST,然后把s到各个连通分量的最小权值的边加上,然后继续加边看看能否使生成树权减小(详见解题报告)。
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
度限制最小生成树代码 摘自POJ1639代码
(3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序 (poj1094) (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) .....