题目：输入n表示n个点，接下来n-1行每行输入一个字母表示起点，和一个k表示有k个点与他相连，该点的名字和此边长度
求他的最小生成树
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <string> #include <map> #include <iomanip> #include <algorithm> #include <queue> #include <stack> #include <set> #include <vector> //const int maxn = 1e5+5; #define ll long long ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} #define MAX INT_MAX #define FOR(i,a,b) for( int i = a;i <= b;++i) #define bug cout<<"--------------"<<endl using namespace std; int ans,n,tail; int pre[500]; struct node { int x,y,z; }edge[5000]; bool cmp(node a,node b) { return a.z<b.z; } int Find(int x) { if(x==pre[x]) return x; return Find(pre[x]); } void clearr() { memset(edge,0,sizeof(edge)); memset(pre,0,sizeof(pre)); ans=0; } int main() { while(scanf("%d",&n)) { if(n==0) break; clearr(); FOR(i,1,n-1) { char a,b; int k,num; //scanf("%c %d",&a,&k); cin>>a>>k; FOR(j,1,k) { //scanf("%c %d",&b,&num); cin>>b>>num; edge[++tail].x=a-64; edge[tail].y=b-64; edge[tail].z=num; } } sort(edge+1,edge+1+tail,cmp); FOR(i,1,n) pre[i]=i; FOR(i,1,tail) { int headx=Find(edge[i].x); int heady=Find(edge[i].y); if(headx==heady) continue; pre[headx]=heady; ans+=edge[i].z; } cout<<ans<<endl; // FOR(i,1,tail) // { // cout<<edge[i].x<<" "<<edge[i].y<<" "<<edge[i].z<<endl; // } } }