题目描述
写给自己看的prim
样例
blablabla
算法1
核心:取集合外的点到集合最短的边
关键的注释都在 代码中
贪心,
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]))
//第一轮让点1加入集合 dist【1】=0
t=j;
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]);
//更新新加入集合t到各个点的距离
}
return res;
}
int main() {
cin>>n>>m;
memset(g,inf,sizeof g);
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;
}