【模板】最小生成树

在无向图中，将所有点联通起来所需要的最小花费的树

Kruscal

贪心取边，能取最小边就取最小边

算法思路

1. 对于一颗树，如果他有n个节点，那么肯定连了n-1条边
2. 要使这颗树的边权之和最小，就贪心取所有边中的小边，而每取一条边就将边链接的两点归为同一个集合(并查集)，而在取之前两个节点就是一个集合的话，这条边就没有贡献，就不取这条边。

算法流程

1. 建图、连边
2. 按边权排序
3. 贪心取边并判是否在同一集合

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+12;
int fa[N],n,m,ans,cnt;
struct node{
  int u,v,w;
}e[N];
int cmp(node a,node b)
{
  return a.w<b.w;
}
int f(int x)
{
  if( x!=fa[x] ) return fa[x]=f(fa[x]);
  return fa[x];
}
void k()
{
  sort(e+1,e+1+m,cmp);
  for(int i=1;i<=n;i++) fa[i]=i;
  for(int i=1;i<=m;i++)
  {
    if(cnt==n-1) break;
    int a=f(e[i].v);
    int b=f(e[i].u);
    if( a==b ) continue;
    fa[a]=b,cnt++,ans+=e[i].w;
  }
  //cout<<cnt<<endl;
  if( cnt==n-1 ) cout<<ans;
  else cout<<"orz";

}

int main(){
  cin>>n>>m;
  for(int i=1;i<=m;i++)
  {
    cin>>e[i].u>>e[i].v>>e[i].w;
  }
  k();



}

Prim

Kruskal是贪心取边，而Prim就是贪心取点。

算法思路

1. 对于一棵树，我们的所有节点肯定都是会取的（如果不能那肯定orz)
2. 每取一个点，我们就记录该点已经被取了，并且将链接该点的边纳入优先队列中

算法流程

1. 建图、连边
2. 将生成树的根节点所连边（任意点，一般纳入1号节点）纳入优先队列中
3. 跑边，每到一个未访问过的节点，就将点数纳入生成树，边权对答案有贡献，答案增加

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+12,M=4e5+12;
int n,m,u,v,w,cnt,tot,use[N],head[N],ans;
struct Edge{
  int nex,to,w;
  bool operator < ( const Edge &other ) const
  {
    return other.w<w;
  }
}edge[M];

void addedge(int u,int v,int w)
{
  cnt++;
  edge[cnt]={ head[u],v,w };
  head[u]=cnt;
}

priority_queue<Edge>q;

void prim(){
  for(int i=head[1];i;i=edge[i].nex)
  {
    q.push(edge[i]);
    use[1]=1;
    tot=1;
  }

  while( !q.empty() )
  {
    Edge l=q.top();
    q.pop();
    int y=l.to,w=l.w;
    if( use[y] ) continue;
    ans+=w;
    tot++;
    use[y]=1;
    for(int i=head[y];i;i=edge[i].nex)
    {
      q.push(edge[i]);
    }
  }
}

int main(){
  cin>>n>>m;
  for(int i=1;i<=m;i++)
  {
    cin>>u>>v>>w;
    addedge(u,v,w);
    addedge(v,u,w);
  }
  prim();
  if( tot==n ) cout<<ans;
  else cout<<"orz";


}