POJ 1258 Agri-Net 【最小生成樹入門題目】

題意;

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define mx 105
using namespace std;
int fa[mx],sum;
int n,ce;
struct aa{
  int x,y,qu;
}ma[mx*mx];    //結構體數組開成2*mx大小，感覺自己是個智障 
void init(){
//  memset(vis, 0, sizeof(vis));
  for(int i = 1; i < mx; i++ )
    fa[i] = i;
  sum=ce=0;
}
bool cmp(aa a,aa b){
  return a.qu<b.qu;
}
int find(int x){
  return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int main(){
  while(scanf("%d",&n)!=EOF){
    init();
    for(int i = 1; i <=n; i++)
      for(int j=1; j <= n; j++){
        ma[ce].x = i;
        ma[ce].y = j;
        scanf("%d",&ma[ce].qu);
        ce++;
      }
    sort(ma,ma+ce,cmp);
    for(int i = 0; i < ce; i++){
      int x = ma[i].x,y = ma[i].y, qu = ma[i].qu;
      int a=find(x),b=find(y);
      if(a == b) continue;
      else{
        fa[a] = b;
        sum += qu; 
      }
    }
    cout<<sum<<endl; 
    
  }
  return 0;
}