MST：最小生成树

  • Kruskal:借助并查集

  • 定义边结构体，构造边

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

const int maxn=25;
int father[maxn];
int height[maxn];

void Initial(int n){
  for(int i=0;i<n;i++){
    father[i]=i;  
    height[i]=1;
  }
}

int Find(int x){
  if(x!=father[x]){
    father[x]=Find(father[x]);
  }
  return father[x];
}

void Union(int a,int b){
  a=Find(a);
  b=Find(b);
  if(a==b)return;
  else if(height[a]>height[b])father[b]=a;
  else if(height[a]<height[b])father[a]=b;
  else{
    father[b]=a;
    height[a]++;
  }
}

struct Edge{
  int From;
  int To;
  int dis;
  Edge(){}
  Edge(int a,int b,int c):From(a),To(b),dis(c){}
  bool operator <(Edge x)const{
    return dis<x.dis;
  }
};

Edge s[76];

int Kruskal(int n,int m){
  int sum=0;
  sort(s,s+m);
  Initial(n);
  for(int i=0;i<m;i++){
    Edge cur=s[i];
    if(Find(cur.From)!=Find(cur.To)){
      sum+=cur.dis;
      Union(cur.From,cur.To);
    }
  }
  return sum;
}

int main(){
  int n,k;
  while(scanf("%d",&n)!=EOF){
    if(n==0)break;
    int i=0;
    for(int u=0;u<n-1;u++){
      getchar();
      char village;
      scanf("%c %d",&village,&k);
    
      char next;
      int d;
      while(k--){
        getchar();
        scanf("%c %d",&next,&d);
        s[i++]=Edge(village-'A',next-'A',d);//保存边
      }
    }
    printf("%d\n",Kruskal(n,i));
    
  }
 
  return 0;
}