题意:
求最小生成树的边长和.
#include <cstdio> #include <vector> #include <algorithm> using namespace std; const int MAXN = 30; int f[MAXN]; int n; typedef struct edge { int u,v,w; edge(){} edge(int _u, int _v, int _w):u(_u),v(_v),w(_w){} }edge; vector<edge> g; bool cmp(edge a, edge b) { return a.w<b.w; } int find_set(int x) { if(f[x]!=x) f[x] = find_set(f[x]); return f[x]; } int Kruskal() { sort(g.begin(),g.end(),cmp); for(int i=0;i<n;i++) f[i] = i; int ans = 0; for(int i=0;i<g.size();i++) { int u = g[i].u, v = g[i].v; u = find_set(u), v = find_set(v); if(u==v) continue; f[u] = v; ans += g[i].w; } return ans; } int main() { while(scanf("%d",&n)==1 && n) { g.clear(); for(int i=0,m;i<n-1;i++) { char c; scanf(" %c %d",&c,&m); for(int j=0,w;j<m;j++) { scanf(" %c %d",&c,&w); g.push_back(edge(i, c-'A', w)); } } printf("%d\n",Kruskal()); } }