题目描述
用prim算法做
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int g[N][N];
int d[N];
int n, m;
bool st[N];
int prim(){
int res = 0;
memset(d, 0x3f, sizeof d);
d[1] = 0;
for(int i = 0; i < n; i ++){
int t = -1;
for(int j = 1; j <= n; j ++){
if(!st[j] && (t == -1 || d[j] < d[t]))
t = j;
}
st[t] = true;
res += d[t];
for(int j = 1; j <= n; j ++){
d[j] = min(d[j], g[t][j]);
}
}
return res;
}
int main(){
cin>>n>>m;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++){
if(i != j) g[i][j] = 1;
else g[i][j] = 0;
}
for(int i = 0; i < m; i ++){
int a, b;
cin>>a>>b;
g[a][b] = g[b][a] = 0;
}
cout<<prim()<<endl;
return 0;
}