百炼1251:丛林中的路（Kruskal）

描述

热带岛屿Lagrishan的首领现在面临一个问题&＃xff1a;几年前&＃xff0c;一批外援资金被用于维护村落之间的道路&＃xff0c;但日益繁茂的丛林无情的侵蚀着村民的道路&＃xff0c;导致道路维修开销巨大&＃xff0c;长老会不得不放弃部分道路的维护。上图左侧图显示的是正在使用道路的简图以及每条路每个月的维修费用&＃xff08;单位为aacms&＃xff09;。现在长老会需要提出一种方案&＃xff0c;即需要保证村落之间都可以互相到达&＃xff0c;又要将每个月的道路维修费用控制在最小。村子编号为从A到I。上图右侧显示的方案最小维修开销为216 aacms每月。

输入输入包含1~100个数据集&＃xff0c;最后一行为0.每个数据集第一行为村落数目n, 1 提示&＃xff1a;蛮力算法虽能找出解决方案&＃xff0c;但将会超出时间限制。样例输入

9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
3
A 2 B 10 C 40
B 1 C 20
0

样例输出

216
30

Kruskal算法模板题

#include
#include
#include
using namespace std;int n;
int cnt&＃61;0;
char fa[200];
int sum&＃61;0;struct node
{char x,y;int dis;
}edg[200];bool cmp(node a,node b)
{return a.dis}void init(int n)
{for(int i&＃61;0;i}char _find(char x)
{if(fa[x]&＃61;&＃61;x){return x;}elsereturn fa[x]&＃61;_find(fa[x]);
}void _union(char x,char y)
{char tempx&＃61;_find(x);char tempy&＃61;_find(y);if(tempx!&＃61;tempy){fa[tempx]&＃61;tempy;}}int main()
{while(cin>>n&&n!&＃61;0){cnt&＃61;0;init(n);for(int i&＃61;0;i>c1>>num;for(int j&＃61;0;j>c2>>d;edg[cnt].x&＃61;c1;edg[cnt].y&＃61;c2;edg[cnt&＃43;&＃43;].dis&＃61;d;}}sort(edg,edg&＃43;cnt,cmp);sum&＃61;0;int a&＃61;0;for(int i&＃61;0;i}