原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1301
样例：
Sample Input
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
0Sample Output
216
30题意： 给定村庄数量n，一系列村庄之间的道路每月维护成本信息，让你计算出让所有村庄连通最少需要维护的成本。
解题思路： 这道题特别的地方就是村庄是利用字母来编号的，但也还是顺序的，所以我们利用ASCII码值即可转换为数字编号，其它就按模板来写就行，注意使用Prim算法要考虑重边，我们具体看代码。这里指路Prim算法和Kruskal算法的讲解博客。（点击链接即可）
Prim算法AC代码：
/* *邮箱：unique_powerhouse@qq.com *blog:https://me.csdn.net/hzf0701 *注：文章若有任何问题请私信我或评论区留言，谢谢支持。 * */
#include<bits/stdc++.h> //POJ不支持#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量，a为初始值，n为界限值，递增
#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量， a为初始值，n为界限值，递减。
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define mp make_pairusing namespace std;const int inf = 0x3f3f3f3f;//无穷大
const int maxn = 29;//最大值。
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
//*******************************分割线，以上为自定义代码模板***************************************//int graph[maxn][maxn];
int dis[maxn];//到集合中的最短距离。
bool vis[maxn];//判断是否已经加入集合中。
int n,t,w;
char ch1,ch2;
void Prim(){//默认从编号为0的开始。vis[0]=true;rep(i,1,n-1){dis[i]=graph[0][i];}int minn,pos,sum=0;rep(i,1,n-1){minn=inf;rep(j,1,n-1){if(!vis[j]&&dis[j]<minn){minn=dis[j];pos=j;}}if(minn==inf)break;vis[pos]=true;sum+=minn;rep(j,1,n-1){if(!vis[j]&&dis[j]>graph[pos][j])dis[j]=graph[pos][j];}}cout<<sum<<endl;
}
int main(){//freopen("in.txt", "r", stdin);//提交的时候要注释掉IOS;while(cin>>n&&n){memset(graph,inf,sizeof(graph));memset(vis,false,sizeof(vis));rep(i,0,n-2){cin>>ch1>>t;rep(j,0,t-1){cin>>ch2>>w;graph[ch2-'A'][ch1-'A']=graph[ch1-'A'][ch2-'A']=min(graph[ch2-'A'][ch1-'A'],w);}}Prim();}return 0;
}Kruskal算法AC代码：
/* *邮箱：unique_powerhouse@qq.com *blog:https://me.csdn.net/hzf0701 *注：文章若有任何问题请私信我或评论区留言，谢谢支持。 * */
#include<bits/stdc++.h> //POJ不支持#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量，a为初始值，n为界限值，递增
#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量， a为初始值，n为界限值，递减。
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define mp make_pairusing namespace std;const int inf = 0x3f3f3f3f;//无穷大
const int maxn = 1e5;//最大值。
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
//*******************************分割线，以上为自定义代码模板***************************************//struct Edge{int u,v;//所连村庄编号。int w;//该条道路维修花费。bool operator <(const Edge &a){//运算符重载。return w<a.w;}
};
Edge edges[maxn];
int n,cnt,temp1,temp2;//n个村庄，cnt为道路数量，即边数。
int father[maxn];//father[i]表示第i个村庄所属的连通分量。
int Find(int x){int r=x;while(r!=father[r])r=father[r];int i=x,j;while(father[i]!=r){j=father[i];father[i]=r;i=j;}return r;
}
void Kruskal(){sort(edges,edges+cnt);rep(i,0,n-1)father[i]=i;int sum=0;rep(i,0,cnt-1){temp1=Find(edges[i].u);temp2=Find(edges[i].v);if(temp1!=temp2){father[temp1]=temp2;sum+=edges[i].w;}}cout<<sum<<endl;
}
char ch1,ch2;
int main(){//freopen("in.txt", "r", stdin);//提交的时候要注释掉IOS;while(cin>>n&&n){cnt=0;rep(i,0,n-2){cin>>ch1>>temp1;rep(j,0,temp1-1){cin>>ch2>>temp2;edges[cnt].u=ch1-'A';edges[cnt].v=ch2-'A';edges[cnt].w=temp2;cnt++;}}Kruskal();}return 0;
}