POJ 1251 Jungle Roads（最小生成树）

题目链接：
POJ 1251 Jungle Roads
题意：
n个点，每个点有m条无向边，每条边有一个权值，求最少的路径权值和使得n个点连通。
分析：
最小生成树裸题。

$CODE$:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;const int maxn=27;int n,uu,vv,ww,m,ans,tot;
int pre[maxn];
char s[5];struct Edge{int u,v,w;
}edge[maxn*maxn];bool cmp(struct Edge a,struct Edge b)
{return a.w<b.w;//按边权值升序排序
}void init()
{tot=0;ans=0;for(int i=0;i<maxn;i++)pre[i]=i;
}int find(int x)
{return pre[x]==x?x:pre[x]=find(pre[x]);
}int main()
{
#ifdef LOCALfreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);
#endifwhile(~scanf("%d",&n)&&n){init();for(int i=1;i<n;i++){scanf("%s%d",s,&m);uu=s[0]-'A'+1;for(int j=1;j<=m;j++){scanf("%s%d",s,&ww);edge[tot].u=uu;edge[tot].v=s[0]-'A'+1;edge[tot].w=ww;tot++;}}sort(edge,edge+tot,cmp);//Kruskal Algorithmfor(int i=0;i<tot;i++){uu=edge[i].u;vv=edge[i].v;ww=edge[i].w;int fu=find(uu);int fv=find(vv);if(fu!=fv){ans+=ww;pre[fu]=fv;}}printf("%d\n",ans);}return 0;
}