最小生成树

约 322 个字 174 行代码 预计阅读时间 3 分钟

稠密图用Prim，稀疏图用Kruskal，完全图且边权基于点权计算，用Boruvka

稠密图Prim复杂度比Kruskal更低，但不一定跑的更快

Kruskal

每个点最初是一个连通块，每次选取边权最小的边，当边连接的是两个不同的连通块，把他们合并成一个连通块，直至生成树中有n个点

$O(ELogE)$

const int N = 2e5 + 3;
const int M = 2e6 + 3;
struct kruskal
{
    struct Edge
    {
        int u, v, w;
        bool operator<(const Edge &f) const
        {
            return w < f.w;
        }
    };
    Edge e[M];
    int tot,n;
    int f[N];
    int find(int x)
    {
        return f[x] == -1 ? x : (f[x] = find(f[x]));
    }
    bool merge(int u,int v)
    {
        u=find(u),v=find(v);
        if(u==v)
            return false;
        f[u]=v;
        return true;
    }
    void init(int nn)
    {
        n = nn;
        tot = 0;
        memset(f, -1, sizeof(int) * (n + 1));
    }
    void addEdge(int u, int v, int w)
    {
        e[tot++] = {u, v, w};
    }
    int run()
    {
        sort(e, e + tot);
        int cnt = 1,cost = 0;
        for (int i = 0;i<tot && cnt<n;++i)
        {
            if(!merge(e[i].u,e[i].v))
                continue;
            cost += e[i].w;
            ++cnt;
        }
        return (cnt==n?cost:-1);
    }
};

Prim

任意点作为生成树的起点，每次选取和生成树中的点距离最小的非生成树中的点，加入生成树，直至生成树中有n个点

$O(VlogV+E)$

const int N = 5e3 + 3;
struct prim
{
    struct Edge//注意顺序，因为优先队列是小根堆，之后同理
    {
        int w,v;
        bool operator>(const Edge &f)const
        {
            return w > f.w;
        }
    };
    vector<Edge> e[N];
    priority_queue<Edge,vector<Edge>,greater<Edge> > q;
    int dis[N],vis[N];
    int n;
    void init(int nn)
    {
        n = nn;
        for(int i=1;i<=n;++i)
            e[i].clear();
        memset(dis,0x3f,sizeof(int)*(n+1));
        memset(vis,0,sizeof(int)*(n+1));
        while(!q.empty())
            q.pop();
    }
    void addEdge(int u, int v, int w)
    {
        e[u].push_back({w,v});
        e[v].push_back({w,u});
    }
    int run()
    {
        dis[1]=0;
        q.push({0,1});
        Edge u;
        int cnt=0,cost=0;
        while(!q.empty() && cnt<n)
        {
            u=q.top();
            q.pop();
            if(vis[u.v])
                continue;
            vis[u.v]=1;
            cost+=u.w;
            ++cnt;
            for(auto &[w,v]:e[u.v])
            {
                if(w>=dis[v])
                    continue;
                dis[v]=w;
                q.push({w,v});
            }
        }
        return (cnt==n?cost:-1);
    }
}pr;

Boruvka

每次处理一个连通块时，它向其他连通块伸出一条最小边权的边，启发式合并两个连通块的点（这里总共花费 $O(nlogn)$）。如果能连成，就加上这个边的贡献，直至连通块数为1。

按照其他人的板子，每次操作是 $O(n)$，由于每进行一次操作，连通块个数会减少一半，减少到1需要 $log n$ 次，所以总共 $O(nlogn)$

我用队列优化需要处理的连通块，似乎是 $O(n)$ ？

while 连通块个数大于1
    for 每个连通块 i
        mn[i] = 连接 i 与其他连通块的最小边权
        if mn[i] 连接两个相同的连通块
            continue;
        ans += mn[i]
        Merge( mn[i] 连接的连通块 )
        连通块个数 --

如果记 $O(T)$ 是计算 mn[i] 的复杂度）这个算法的复杂度是 $O(nT+nlogn)$

int a[N];//点权，1-index
namespace boruvka
{
    int n,f[N];
    vector<int> connectBlock[N];//连通块 i 包含的点权(或点)
    queue<int> q;//待处理的点（连通块）
    int find(int x)
    {
        return f[x] ==0 ? x : (f[x] = find(f[x]));
    }
    bool merge(int u,int v)//启发式合并维护连通块包含的点
    {
        u=find(u),v=find(v);
        if(u==v)
            return false;
        if(connectBlock[u].size()<connectBlock[v].size())
            swap(u,v);
        for(int &x:connectBlock[v])
            connectBlock[u].push_back(x);
        connectBlock[v].clear();
        f[v]=u;
        return true;
    }
    void init(int nn)
    {
        n = nn;
        for(int i=1;i<=n;++i)
            q.push(i);
        for(int i=1;i<=n;++i)
            connectBlock[i].push_back(a[i]);
    }
    array<int,2> cal(int x)
    {
        //根据题目计算最小边权和对应的点
        return {0,0};
    }
    ll run()
    {
        array<int,2> res;//边权，连接的另一个点（连通块），顺序不能错
        int u,com=n;//连通块数
        ll ans=0;
        while(com>1)
        {
            while(connectBlock[q.front()].empty())
                q.pop();
            u=q.front();
            q.pop();
            res={INF,0};
            for(int &v:connectBlock[u])
                res=min(res,cal(v));
            if(!merge(u,res[1]))
                continue;
            q.push(u);
            ans+=res[0];
            --com;
        }
        return ans;
    }
};