弃暗投明克鲁斯卡尔吧
by jiaangk @ 2017-07-04 12:34:09
```cpp
#include <iostream>
using namespace std;
const int inf=0x3f3f3f3f;
int n;
int a[110][110];
int path[110]={0};
int f[110]={0};
int dis[110];
int main(){
cin>>n;
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
cin>>a[i][j];
}
}
int u=1;
for (int i=1;i<=n;i++){
if (i==u) dis[i]=0;
else dis[i]=inf;
}
for (int i=1;i<=n;i++){
int mind=inf;
int k;
for (int j=1;j<=n;j++){
if (!f[j] && dis[j]<mind) {
mind=dis[j];
k=j;
}
}
f[k]=1;
for (int j=1;j<=n;j++){
if (!f[j] && a[k][j]<dis[j]) {
dis[j]=a[k][j];
path[j]=k;
}
}
}
int MST=0;
for (int i=1;i<=n;i++) MST+=dis[i];
cout<<MST;
return 0;
}
```
by Flokirie @ 2017-07-29 20:18:50