prim算法。。。。。。。
嘛，这就是个暴力。。。。。。
首先，初始化起点-----
因为是最小生成树，所以就有（总点数-1）条有用边
我们设di为以i为一点的在所求的最小生成树上的一边
首先，
我们先找到一个最小的且<stron> </stron>
就搞定了。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
漏了一个证明（为什么更新答案时能确保答案正确。。。。）
嘛，这个你只要想着prim的过程就是逐渐完善答案的过程。。。。。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
long long maxl=9999999;
int p[10005][10005];
int d[1000005];
bool vis[1000005];
long long ans=0;
void prim(int begin){ for(int i=0;i<=n;i++){ d[i]=maxl; vis[i]=false; } d[begin]=0; int minl,k; for(int i=1;i,=n;i++){ for(int j=1;j<=n;j++){ if(vis[j]==false&&minl>p[j]){ minl=p[j]; k=j; } } vis[k]=true; for(int j=1;j<=n;j++){ iof(vis[j]==false&&p[k][j]<d[j])d[j]=p[k][j]; } } }
int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ p[i][j]=maxl; } } for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; p[u][v]=min(p[u][v],w); p[v][u]=min(p[v][u],w); } prim(1); for(int i=1;i<=n;i++){ //cout<<d[i]<<" "<<i<<endl; ans+=d[i]; } cout<<ans<<endl; }
查看15道真题和解析
字节跳动公司氛围 553人发布