生成树
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;
}