题解 P4716

· · 题解

估值快没了，赶紧写篇题解水水。

传送门。

本文将会讲到 \texttt{Tarjan} 的优化朱刘算法。这种方法是我从所看过的博客中理解的，有可能有些地方我理解错了，请在评论区或私信中提出。

大家都知道朱刘算法可以做到 O(nm) 求最小树形图，那有没有更快的做法呢？\texttt{Tarjan} 的优化朱刘算法便可以做到 O((n+m)\log m) 求最小树形图。

这个算法是对朱刘的优化，那么我们来看看朱刘算法主要有哪些步骤：

  1. 求最短弧集。
  2. 找环并缩环。
  3. 判定无解。

1. 维护最短弧集：

设以 x 为终点的边的集合为 E_x，E_x 中边权最小值为 E_{x_{\min}}。

在朱刘算法中关于最短弧集的操作有一下几种：

  1. 查找 E_{x_{\min}}。
  2. 找到一个环，把一个环内的节点 a_1,a_2,...,a_k 缩为 p，把集合 E_{a_x} 中所有值减去 E_{a_{x_{\min}}}，把 E_{a_{x_{\min}}} 从集合 E_{a_x} 中删去，把集合 E_{a_1},E_{a_2},...,E_{a_k} 合并为 E_p。

我们把这些东西抽象化，那就变为 3 种操作：

  1. 查询最小值。
  2. 整体减一个数。
  3. 合并几个集合。

根据这些，我们可以发现，可并堆这种数据结构可以十分优秀地维护这些操作。

2. 找环与缩环：

朱刘算法中结束的标志是没有环，但是这个条件未免过于苛刻，很难快速判断。那么我们干脆直接把它进阶，变为缩成一个点，也就是整张图没有边。

但是原图不可能一定强连通，那么我们需要强行使其变为强连通，就是加 n 条边权为 INF 的边。

我们用一个栈进行存储，每次将栈顶 x 的最短弧的起点 y 压入栈。如果 y 不在栈中，压入即可；否则说明找到一个环，在栈中把环弹出，把环缩为一个点 p。

在加答案时如果终点是 r 或含有 r 的环，那么这条边不能计入答案。因为最小树形图 r 没有入边。

因为要找一个点被收缩多次后的新点，所以需要一个并查集来维护。

3. 判定无解：

因为边权为 INF 的边是新加入的，如果答案大于 INF 则说明我们用了新加的边，也就是说原图无法形成最小树形图，即无解。

代码只有 99 行，带有注释，请放心食用：

#include<iostream>
#include<cstring>
using namespace std;
#define int long long
const int N=1e6+10,INF=0x3f3f3f3f;
struct ltt_node{
    int lson,rson;
    int val,tag;
    int from,to;
    int dis;
};
struct leftist_tree{
    ltt_node ltt[N];
    int tot;
    inline int newnode(int val,int from,int to){
        tot++;
        ltt[tot].val=val;
        ltt[tot].from=from;
        ltt[tot].to=to;
        return tot;
    }
    inline void pushdown(int now){
        int ls=ltt[now].lson,rs=ltt[now].rson;
        ltt[ls].val+=ltt[now].tag;
        ltt[rs].val+=ltt[now].tag;
        ltt[ls].tag+=ltt[now].tag;
        ltt[rs].tag+=ltt[now].tag;
        ltt[now].tag=0;
    }
    int merge(int x,int y){
        if(!x||!y) return x+y;
        pushdown(x),pushdown(y);
        if(ltt[x].val>ltt[y].val) swap(x,y);
        ltt[x].rson=merge(ltt[x].rson,y);
        if(ltt[ltt[x].rson].dis>ltt[ltt[x].lson].dis)
            swap(ltt[x].lson,ltt[x].rson);
        ltt[x].dis=ltt[ltt[x].rson].dis+1;
        return x;
    }
    int del(int rt){
        pushdown(rt);
        int ls=ltt[rt].lson;
        int rs=ltt[rt].rson;
        return merge(ls,rs);
    }
};//左偏树基本操作
leftist_tree ltt;
int root[N],fa[N];
int sta[N],top;
bool vis[N];
inline int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}//并查集，用于查找一个点被收缩多次后的新点
signed main(){
    int n,m,r;
    cin>>n>>m>>r;
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        int lp=ltt.newnode(z,x,y);//新建一个左偏树节点，边从x到y，边权为z
        root[y]=ltt.merge(root[y],lp);//插入到y的左偏树中
    }
    for(int i=1;i<=n;i++){
        int x=i,y=i%n+1;
        int p=ltt.newnode(INF,x,y);
        root[y]=ltt.merge(root[y],p);
    }//加入n条边强行使其强连通
    for(int i=1;i<=2*n;i++) fa[i]=i;//算上收缩的点共有2n个点
    sta[++top]=r,vis[r]=true;
    int ans=0,cnt=n;
    while(root[sta[top]]){//还有边
        int lp=root[sta[top]];
        ltt_node tmp=ltt.ltt[lp];
        int u=find(tmp.from);
        if(u==sta[top]){
            root[sta[top]]=ltt.del(root[sta[top]]);
            continue;
        }//自环
        if(!vis[u]){
            sta[++top]=u;
            vis[u]=true;
            continue;
        }//不构成环，加入即可
        int p=++cnt;//把环缩为p
        while(vis[u]){//u还没被弹出
            int v=sta[top--];//环上的节点
            vis[v]=false,fa[v]=p;//这个点缩成了p
            int val=ltt.ltt[root[v]].val;//最短弧的边权
            ltt.ltt[root[v]].tag-=val;//懒标记
            int x=find(ltt.ltt[root[v]].to);
            ans+=(x!=find(r))*val;//如果x等于r，说明这条边通向r，不能选
            root[v]=ltt.del(root[v]);//删掉最短弧
            root[p]=ltt.merge(root[p],root[v]);//合并到p的左偏树上
        }//把整个环找出来
        sta[++top]=p;
        vis[p]=true;//把p加入
    }
    cout<<(ans>=INF?-1:ans)<<'\n';
}

总共有 2n 个点，合并的时复为 O(n\log m)，每条边都会访问一次，每次访问要 O(\log m)，时复为 O(m\log m)，总时复为 O((n+m)\log m)。

参考资料：

OI Wiki-最小树形图。

yybakioi 的博客-题解 P4716 【【模板】最小树形图】。