Jungle Roads

套用Kruskal或Prim的模板即可。这里我用的时Kruskal。

代码如下：

#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <iostream>
#define INF 0x3f3f3f3f
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef struct{
    int from,to,cost; 
}edge;
edge arr[100];
int pre[100];
int n;
int cnt;
bool cmp(edge e1,edge e2)
{
    return e1.cost<e2.cost;
}
void init()
{
    for(int i=1;i<=n;i++)
        pre[i]=i;
}
int findr(int x)
{
    if(x==pre[x])
        return x;
    return pre[x]=findr(pre[x]);
}
int kruskal()
{
    int rsl=0;int num=0;
    init();
    for(int i=0;i<cnt;i++)
    {
        int fx=findr(arr[i].from);
        int fy=findr(arr[i].to);
        if(fx!=fy)
        {
            pre[fx]=fy;
            rsl+=arr[i].cost;
        }
    }
    return rsl;
}
int main()
{
    while(cin>>n&&n)
    {    
        cnt=0;
        for(int i=0;i<n-1;i++)
        {        
            char ch,ch1;
            int k,aacm;
            cin>>ch>>k;
            getchar();
            for(int j=1;j<=k;j++)
            {    
                edge tmp;
                cin>>ch1>>aacm;
                getchar();
                tmp.from=ch-'A'+1;
                tmp.to=ch1-'A'+1;
                tmp.cost=aacm;
                arr[cnt++]=tmp;
            }
        }
        sort(arr,arr+cnt,cmp);
        int ans=kruskal();
        printf("%d\n",ans);
    }
    return 0;
}