题解 | #畅通工程#

MST：最小生成树

Kruskal:借助并查集

• 定义边结构体，升序，依次合并不在同一连通集里的点

• 最后遍历所有结点，检查是否全部连通

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

const int maxn=101;
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 x,int y){
  int a=Find(x);
  int b=Find(y);
  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 Road{
  int From;
  int To;
  int Cost;
  bool operator <(Road x)const{
    return Cost<x.Cost;
  }
};

Road s[maxn*maxn];

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

int main(){
  int n,m;
  while(scanf("%d%d",&m,&n)!=EOF){
    if(n==0)break;
    for(int i=0;i<m;i++){
      scanf("%d%d%d",&s[i].From,&s[i].To,&s[i].Cost);
    }
    int sum=Kruskal(n,m);
      bool flag=true;//全部连通标记
      int root=Find(1);
      for(int i=2;i<=n;i++){
          if(Find(i)!=root){
              flag=false;
              break;
          }
      }
    if(!flag)printf("?\n");
    else printf("%d\n",sum);
  }
  return 0;
}