AcWing 858. Prim算法求最小生成树
原题链接
简单
作者:
幼稚小人
,
2020-12-22 23:42:34
,
所有人可见
,
阅读 459
图论 Prim 细节 try
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 510, inf = 0x3f3f3f3f;
int n, m,u, v, w;
int g[N][N], dist[N];
bool vis[N];
//稠密图
int prim() {
//memset(dist,inf,sizeof dist);
//menset 对于char类型赋值 对于int型只能0,1,inf
fill(dist,dist+N,inf);
int res=0;
dist[1]=0;
for(int i=0;i<n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(!vis[j] && (t==-1 || dist[j]<dist[t]))
t=j;
//未加入集合s并且比较j和t的距离
}
if(dist[t]==inf) return inf;
res+=dist[t];
vis[t]=true;
for(int j=1;j<=n;j++){
dist[j]=min(dist[j],g[t][j]);
//在原来的基础上只要和新来的加入集合s的t点作比较就可以了
}
}
return res;
}
int main() {
cin >> n >> m;
fill(g[0], g[0] + N * N, inf);
// for(int i = 1; i <= n; i++)
// for(int j = 1; j <= n; j++)
// if(i ==j) g[i][j] = 0;
// else g[i][j] = inf;
while(m--) {
cin >> u >> v >> w;
g[u][v] = g[v][u] = min(g[u][v], w);
}
int t = prim();
if(t == inf) puts("impossible");
else cout << t << endl;
}