本文共 927 字，大约阅读时间需要 3 分钟。
题意分析：
模板题了吧。
#include#include #include #include using namespace std;#define MAX 30struct edge { int u, v, cost; };bool cmp(const edge& e1, const edge& e2) { return e1.cost < e2.cost; }vector es;//边集合int fa[MAX];//并查集int n;//顶点数int find(int x) { return fa[x] == -1 ? x : fa[x] = find(fa[x]); }//并查集查找 路径压缩int kk(){ int cnt = 0; sort(es.begin(), es.end(), cmp);//对边进行排序 memset(fa, -1, sizeof(fa));//并查集初始化 int res = 0; for (int i = 0; i < es.size(); i++) { if (find(es[i].u) != find(es[i].v))//不在同一个连通分量 { fa[find(es[i].u)] = find(es[i].v);//unite res += es[i].cost; } } return res;}int main(){ int n; while (cin >> n,n) { es.clear(); for (int i = 0; i < n - 1; i++) { char c1, c2; int k,v,d; cin >> c1 >> k; while (k--) { cin >> c2 >> d; v = c2 - 'A'; edge tmp = { i,v,d }; es.push_back(tmp); } } cout << kk() << endl; } system("pause");}
转载地址：http://fuyci.baihongyu.com/