生成树

prim 模板
P1546 [USACO3.1] 最短网络 Agri-Net

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m, vis[105], d[105], xk, a[105][105], ans,fl;
void prim(){//n^2
  vis[1] = 1; int k = 1;
  for(int i = 1; i <= n-1; i++){
    int mne = 0x7f7f7f7f;
    for(int j = 1; j <= n; j++){
      if(!vis[j]){
        if(a[k][j] < d[j])
          d[j] = a[k][j];//err: xk = j;
        if(d[j] < mne)
          mne = d[j], xk = j;
      }
    }
    k = xk; vis[k] = 1;
    ans += mne;
  }
}
int x,y,z;
int main(){
  scanf("%d",&n);
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++){
      scanf("%d",&a[i][j]);
      a[j][i] = a[i][j];
    }
  memset(d,0x7f,sizeof d);
  prim();
  printf("%d\n",ans);
  return 0;
}