- 一道最小生成树的模板题
刚开始建好图之后,后续再进行输入已经建好的路时,同时更新一下,且该路的权值为0.
//prim算法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 105, INF = 0x3f3f3f3f;
int n, g[N][N], vis[N], dist[N], res;
int prim(){
memset(dist, INF, sizeof dist);
for(int i = 0; i < n; i ++){
int t = -1;
for(int j = 1; j <= n; j ++)
if(!vis[j] && (t == -1 || dist[t] > dist[j]))
t = j;
if(i) res += dist[t];
for(int j = 1; j <= n; j ++)
dist[j] = min(dist[j], g[t][j]);
vis[t] = true;
}
}
int main(){
cin >> n;
memset(g, INF, sizeof g);
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++){
int w;
cin >> w;
g[i][j] = g[j][i] = min(g[i][j], w);
}
}
int q;
cin >> q;
while(q --){
int u, v;
cin >> u >> v;
g[u][v] = g[v][u] = 0;
}
cout << prim() << endl;
return 0;
}