Kruskal求最小（大）生成树

模板

思路：将边排序，依次向并查集里加边，并且保证此边连接的两个结点不在一个并查集里，加到N-1（N为图中结点数）条边时，就生成了最小生成树

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int ecnt;
struct node{int from,to,value;} edge[100001];
void add(int from,int to,int value)
{
    ecnt++;
    edge[ecnt].from=from;
    edge[ecnt].to=to;
    edge[ecnt].value=value;
}
int fath[100001];
int getfath(int x)
{
    if(fath[x]==x) return x;
    return fath[x]=getfath(fath[x]);
}
void unionset(int x,int y){fath[getfath(x)]=getfath(y);}
int cmp(const node &a,const node &b)
{
    if(a.value<b.value) return true;
    else return false;
}
long long mstv=0,biancnt=0;
int main()
{
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    int from,to,value;int x;
    for(int i=1;i<=m;i++)
    {
        cin>>from>>to>>value;
        add(from,to,value);
    }
    for(int i=1;i<=n;i++) fath[i]=i;
    sort(edge+1,edge+ecnt+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(getfath(edge[i].from)!=getfath(edge[i].to))
        {
            unionset(edge[i].from,edge[i].to);
            mstv+=edge[i].value;
            biancnt++;
        }
        if(biancnt==n-1) break;
    }
    cout<<mstv;
    return 0;
}

例题

UVa1395 Slim_Span

所谓的Slim Span即为最大边与最小边差值最小的生成树，与最小生成树问题的思路相似

先对边升序排序，对于一个连续的边区间$[L,R]$，从小到大枚举L，对于每个L，从小到大枚举R，依次向并查集里加边，加个判断：如果目前的这些边已经使得图连通，就停止枚举，并更新最小值。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=100,MAXM=50*99,INF=1<<30;
struct node2{int u,v,w;} a[MAXM+1];int acnt;
void add2(int u,int v,int w){++acnt,a[acnt].u=u,a[acnt].v=v,a[acnt].w=w;}
int fa[MAXN+1];
int getfa(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=getfa(fa[x]);
}
void join(int x,int y)
{
    fa[getfa(x)]=getfa(y);
}
bool cmp(const node2 & a,const node2 & b){return a.w<b.w;}
int N,M;
int main()
{
    int i;
    while(cin>>N>>M&&N)
    {
        acnt=0;
        for(i=1;i<=N;i++) fa[i]=i;
        for(i=1;i<=M;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add2(u,v,w);
        }sort(a+1,a+M+1,cmp);
        int L,R;
        int minv=INF;
        for(L=1;L<=M-(N-1)+1;L++)
        {
            for(i=1;i<=N;i++) fa[i]=i;
            int times=0;
            for(R=L;R<=M;R++)
                if(getfa(a[R].u)!=getfa(a[R].v))
                {
                    join(a[R].u,a[R].v);
                    ++times;
                    if(times==N-1)
                    {
                        minv=min(minv,a[R].w-a[L].w);
                        break;
                    }
                }
        }
        if(minv==INF) cout<<-1<<endl;
        else cout<<minv<<endl;
    }
    return 0;
}