这题，简单的最小生成树问题。
只是输入的时候比较麻烦，一开始的N，是村庄的个数，，下面N – 1 条信息，一开始的大写字母S和数K，是S村庄有K条路连接，后面是K个村庄以及权值。
处理好了输入的数据，就很简单了。
下面的是AC的代码：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;class data{public:int from, to, cost;};data Road[100];int n, count1;int par[30];int cmp(data &a, data &b)//权值从小到大排{return a.cost < b.cost;}int finds(int x)//并查集查找函数{if(par[x] == x)return x;elsereturn par[x] = finds(par[x]);}void unite(int x, int y)//合并函数{x = finds(x);y = finds(y);if(x == y)return;elsepar[y] = x;}int same(int x, int y)//判断是否属于同一个并查集{return finds(x) == finds(y);}int solve()//构造最小生成树函数{int res = 0;for(int i = 0; i < count1; i++){data d = Road[i];if(!same(d.from, d.to)){unite(d.from, d.to);res += d.cost;}}return res;}int main(){//freopen("data.txt", "r", stdin);int i, j, k, a, w;char s;while(scanf("%d", &n) != EOF && n)//输入的处理{getchar();count1 = 0;for(i = 0; i < 30; i++)par[i] = i;for(i = 0; i < n – 1; i++){scanf("%c%d", &s, &k);a = s – 'A';getchar();for(j = 0; j < k; j++){scanf("%c%d", &s, &w);Road[count1].from = a; Road[count1].to = s – 'A'; Road[count1].cost = w;count1++;getchar();}}sort(Road, Road + count1, cmp);int ans = solve();printf("%d\n", ans);}return 0;}
我想一个人旅行，可以不带相机，也不要带上手机，
