题解 | #Jungle Roads#

英语太难啦，大致意思是这样的：

一个部落有n个村子，若干条道路，每个道路有它的花费，要修一条可以连接所有村子的路，保证花费最小，典型的最小生成树。 用例第一行是n个村子，之后的n-1行是道路信息

A 2 B 12 I 25

这代表有两条路通往村子A，AB之间的花费是12，AI之间的花费是25。这个理解了就好做多了

C++代码：

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N=100;
int T[N];
int find(int x) {
    if(T[x]==-1) return x;
    else {
        int temp=find(T[x]);
        T[x]=temp;
        return temp;
    }
}
struct Edge{
    int a,b;
    int cost;
    bool operator<(const Edge& A) const {
        return cost<A.cost;
    }
}e[100];

int main() {
    int n;
    char s;
    while(scanf("%d",&n)!=EOF&&n!=0) {
        int size=0;
        int ncmp=n-1;   //个数
        while(ncmp--) {
            cin>>s;  //起点
            int xnum; //边的个数
            scanf("%d",&xnum); //边的个数
            int a=s-'A'+1; //起点序号
            while(xnum--) { 
                cin>>s;  //终点
                int x; //起点->终点的路径长度
                scanf("%d",&x); //起点->终点的路径长度
                int b=s-'A'+1; //终点序号
                e[size].a=a;
                e[size].b=b;
                e[size].cost=x;
                size++;
            }
            
        }
        int ans=0;
        sort(e,e+size);
        for(int i=1;i<=n;i++) T[i]=-1;
        for(int i=0;i<size;i++) {
            int a=find(e[i].a);
            int b=find(e[i].b);
            if(a!=b) {
                T[a]=b;
                ans+=e[i].cost;
            }
        }
        printf("%d\n",ans);
    }
}

专题：最小生成树

这里是我梳理的最小生成树的题目： https://blog.nowcoder.net/detail/87ca35ff43d24f70bc6f858505ccb770