最小生成树模板
1.prim算法O(n^2)
思路:
其实和dijkstra算法一样,每次从没用过的点中找一个到集合距离最短的点
然后用这个点去松弛其他的点,如此往复
代码也和dijkstra很像
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N=5010,M=1e5+10;
typedef long long ll;
typedef pair<int,int> pii;
int n,m,k,p,s;
int g[N][N];
int dist[N];
bool st[N];
void prim()
{
int sum=0;
memset(dist,0x3f,sizeof dist);
dist[1]=0;
bool flag=true;
for(int i=1;i<=n;i++)
{
int dis=0x3f3f3f3f;
int id=-1;
for(int j=1;j<=n;j++)
{
if(!st[j]&&dist[j]<dis)
{
dis=dist[j];
id=j;
}
}
if(id==-1)
{
flag=false;
break;
}
st[id]=true;
sum+=dist[id];
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],g[id][j]);
}
if(flag) cout<<sum<<endl;
else cout<<"orz"<<endl;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=0x3f3f3f3f;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);
}
prim();
return 0;
}
2.kruskal算法O(mlogm)
Kruskal算法在解决稀疏图时,比prim快很多
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N=5010,M=2e5+10;
typedef long long ll;
typedef pair<int,int> pii;
int n,m,k,p,s;
int g[N][N];
int dist[N];
bool st[N];
int f[N];
struct Node
{
int x,y,l;
bool operator<(const Node&i) const
{
return l<i.l;
}
}node[M];
int find(int x)
{
if(f[x]!=x) return f[x]=find(f[x]);
return f[x];
}
void kruskal()
{
int sum=n,cnt=0;
for(int i=1;i<=m;i++)
{
int a=find(node[i].x),b=find(node[i].y);
if(a!=b)
{
sum--;
cnt+=node[i].l;
f[a]=b;
}
if(sum==1)
{
cout<<cnt;
return ;
}
}
cout<<"orz";
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
node[i]={a,b,c};
}
sort(node+1,node+m+1);
kruskal();
return 0;
}
3.既然prim算法和dijkstra算法很像,那prim算法也应该存在堆优化版
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N=5010,M=2e5+10;
typedef long long ll;
typedef pair<int,int> pii;
int n,m,k,p,s;
int g[N][N];
int dist[N];
bool st[N];
int f[N];
void prim()
{
memset(dist,0x3f,sizeof dist);
priority_queue<pii,vector<pii>,greater<pii>> q;
q.push({0,1});
dist[1]=0;
int dis=0;
int cnt=0;
while(!q.empty()&&cnt<n)
{
auto t=q.top(); q.pop();
int tmp=t.second;
if(st[tmp]) continue;
dis+=t.first;
cnt++;
st[tmp]=true;
for(int i=1;i<=n;i++)
{
if(!st[i]&&dist[i]>g[tmp][i]) //进是谁都可以进,但是更新别人的点只能选那些没选过的
{
dist[i]=g[tmp][i];
q.push({dist[i],i});
}
}
}
if(cnt==n) cout<<dis;
else cout<<"orz";
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=0x3f3f3f3f;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);
}
prim();
return 0;
}