最小生成树

最小生成树就是：在一张图中，我们将

Prim

从一个节点开始，依次贪心地取它的边权最小的几个边，如果取的边连接的点没有被加到树中，加入这个点，答案加上这个边权，知道所有的点都被加入到树上为止。

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";
}

Kruskal

Prim是贪心加点，这个就是贪心加边。

首先，我们对所有的边进行排序，然后贪心地取边，如果这个边的两个节点 u、v不是在一棵树上（并查集），那么这个边就可以取，反之则不能

Code

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

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

int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++) fa[i]=i;
  for(int i=1;i<=m;i++)
  {
    cin>>u>>v>>w;
    addedge(u,v,w);
    addedge(v,u,w);
  }
  sort(edge+1,edge+1+2*m);
  for(int i=1;i<=1+2*m;i++)
  {
    u=edge[i].from,v=edge[i].to,w=edge[i].w;
    int a=find(u),b=find(v);
    if( a!=b )
    {
      tot++;
      ans+=w;
      fa[a]=b;
    }
  }
  if( tot==n-1 ) cout<<ans;
  else cout<<"orz";
}