题解 | #继续畅通工程#

MST：最小生成树

• 已修建视为成本为0

• 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",&n)!=EOF){
    m=n*(n-1)/2;
    if(n==0)break;
    for(int i=0;i<m;i++){
      int tag;
      scanf("%d%d%d%d",&s[i].From,&s[i].To,&s[i].Cost,&tag);
      if(tag==1)s[i].Cost=0;//已修建视为对应成本为0
    }
    int sum=Kruskal(n,m);
     printf("%d\n",sum);
  }
  return 0;
}