最小生成树 kruscal 堆优化 板子

每次都取出权值最小的边 并且保证他不会出现环(用并查集维护)

最小边用堆维护

#include<bits/stdc++.h>
#include<iostream>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const int NS=5e5+10;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
ll mod=19260817;
struct E
{
ll to,w,next=-1,start;
}e[500005];
ll head[5005];
ll cha[5005];
ll ge[5005];
ll dis[200005];
bool flag[200005];
struct cmp
{
bool operator()(P a,P b)
{
return a.second>b.second;
}
};
int finds(int a)
{
if(cha[a]==a)
return a;
else
{
cha[a]=finds(cha[a]);
return cha[a];
}
}

void unions(int a,int b)
{
int aa=finds(a);
int bb=finds(b);
if(aa==bb)
return ;
else
{
cha[aa]=bb;
ge[bb]+=ge[aa];
}
}
priority_queue< P,vector<P>,cmp> que;
int main()
{

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cha[i]=i;
ge[i]=1;
}
int heads=1;
while(m--)
{
ll temp,s,t;
cin>>s>>t>>temp;
e[heads].start=s;
e[heads].to=t;
P a(heads,temp);
heads++;
que.push(a);
}
ll sum=0,flag=1;
while(!que.empty())
{
P temp=que.top();
que.pop();
int edge=temp.first;
if(finds(e[edge].start)==finds(e[edge].to))
continue;
sum+=temp.second;
unions(e[edge].start,e[edge].to);
if(ge[finds(e[edge].start)]==n||ge[finds(e[edge].to)]==n)
{
flag=0;
break;}
}
if(flag)
cout<<"orz";
else
cout<<sum;

}

最小生成树 kruscal 堆优化 板子

原文：https://www.cnblogs.com/donkey9/p/14881022.html