本文主要是介绍hdu 1301 Jungle Roads （基础最小生成树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
链接：点击打开链接
题意：
对n个村庄之间的路进行修理， 然后是n-1行，每行的第一组数据时一个大写字母VIL和一个数K，Vil表示从这个村庄出发，K表示刚才的那个字母代表的村庄和其他村庄的路的数目，接下来在同一行是K组数据，每组是一个大写字母和一个数，大写字母表示和第一个村庄连接的村庄，数表示维修他们之间的路所需的费用。现在为了使维修费油最低，只需所维修的路使每个村庄都是直接或间接的连接即可，求最小的费用。
思路：
只需把输入数据处理好即可。其他都是kruskal模板。‘
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;struct node{int a,b,cost;
}edge[120];int root[30];
int r[80];
int n;int cmp(node x,node y)
{return x.cost < y.cost;
}int find(int x)
{return root[x] == x ? x : root[x] = find(root[x]);
}void kruskal(int m)
{int ans = 0;for(int i=1; i<=n; i++)root[i] = i;sort(edge,edge+m,cmp);for(int i=0; i<m; i++){int x = find(edge[i].a);int y = find(edge[i].b);if(x != y){ans += edge[i].cost;root[x] = y;}}printf("%d\n",ans);
}int main()
{//freopen("input.txt","r",stdin);int ct,k;char vil,vil_1;while(scanf("%d",&n) != EOF && n){ct = 0;for(int i=1; i<n; i++){getchar();scanf("%c %d",&vil,&k);for(int i=1; i<=k; i++){getchar();scanf("%c %d",&vil_1,&edge[ct].cost);edge[ct].a = vil - 'A' + 1;edge[ct].b = vil_1 - 'A' + 1;ct++;}}kruskal(ct);}return 0;
}
--------------------------------------------------------------------------------------
战斗，永不停歇~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
这篇关于hdu 1301 Jungle Roads （基础最小生成树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
