最小生成树
Prim (朴素版)
#include <bits/stdc++.h>
using namespace std;
const int N=510;
int g[N][N];
int dist[N];
bool st[N];
int n,m;
int prim(){
int res=0;
memset(dist,0x3f,sizeof dist);
for(int i=0;i<n;i++){
int t=-1;
for(int j=1;j<=n;j++)
if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j; // t 没有连通起来,但是距离连通部分最近的点;
if(i&&dist[t]==0x3f3f3f3f) return 0x3f3f3f3f;
if(i) res+=dist[t]; //距离加起来
st[t]=true; //标记已经访问过
for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);//更新 dist ;
}
return res;
}
int main(){
cin>>n>>m;
memset(g,0x3f,sizeof g);
for(int i=1;i<=m;i++)
{
int a,b,w;
cin>>a>>b>>w;
g[a][b]=g[b][a]=min(g[a][b],w);
}
int t=prim();
if(t>=0x3f3f3f3f) cout<<"impossible";
else cout<<t;
return 0;
}
Prim (堆优化版)
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> Pii;
const int N = 1e6+10;
int h[N],w[N],e[2*N],ne[2*N],idx;
int dist[N];
bool st[N]; // 如果为true说明这个点的最短路径已经确定
int n, m;
void add(int a,int b,int c){ //将b插入头结点为a的链表中去
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int prim()
{
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
priority_queue<Pii, vector<Pii>, greater<Pii>> heap;
heap.push({ 0, 1 });
int res=0,len=0;
while(heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if(st[ver]) continue;
st[ver]=true;
res+=distance;
len++;
for(int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if(!st[j])
{
heap.push({ w[i], j });
}
}
}
if(len!=n) return 0x3f3f3f3f;
return res;
}
int main()
{
memset(h, -1, sizeof(h));
cin>>n>>m;
while (m--)
{
int a,b,w;
cin>>a>>b>>w;
add(a,b,w); //无向图
add(b,a,w);
}
int ans=prim();
if(ans==0x3f3f3f3f)
cout<<"impossible"<<endl;
else
cout<<ans<<endl;
return 0;
}
Kruskal
#include <bits/stdc++.h>
using namespace std;
const int N=2*1e5+10;
int n,m;
int p[N];
struct T{
int a,b,c;
bool operator<(const T &W) const{
return c<W.c;
}
}e[N];
int find(int x){
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
e[i]={a,b,c};
}
sort(e+1,e+m+1);
int res=0,cnt=0;
for(int i=1;i<=n;i++) p[i]=i;
for(int i=1;i<=m;i++){
auto [a,b,c]=e[i];
a=find(a),b=find(b);
if(a!=b) {
p[a]=b;
res+=c;
cnt++;
}
}
if(cnt<n-1) cout<<"impossible";
else cout<<res;
return 0;
}
大佬!!!!ddw