题解：P15690 [ICPC 2023 Jakarta R] Contingency Plan 2

· · 题解

怎么没题解，我来写一发。

首先转换一下题面。这个题目要求的实际上就是通过增加最小的边数，使得这个图的拓扑序唯一，并给出构造方案。

发现拓扑序唯一，那么按这个拓扑序走的路径同时也是一条哈密顿路径，那么我们的目标转换为通过增加最小的边数使得原图存在一条哈密顿路径。

根据哈密顿路径的性质，这条哈密顿路径有 n-1 条边（废话），那么肯定是有些边在原图中被用到了。

由于我们需要添加最少边，那么我们肯定希望原图的边被包含得越多越好，所以我们需要找到若干条链，使得任意两条链上的边无交集（如果有交集就构成不了唯一拓扑序了）。

又因为这个原图是个 DAG，所以转化为 DAG 最小路径覆盖问题。使用二分图最大匹配即可求解出原图被用到的最大路径数量。

然后对于第二问，我们需要构造一个方案。这也很简单，由于匹配的边包含了所有点，并且都是链状，所以我们的构造方案就显而易见了，让这些链首尾相连即可。

所以你需要在跑完二分图匹配以后去记录每一条链的首尾，并且记录每一个点属于哪条链的。

但是这里又有一个问题：剩下的原图没有用到的边会限制这些链的连接顺序。但是你发现这是个拓扑排序的问题。于是你把一条链缩成一个点，同一条链里的两个点不用连边。然后跑一遍拓扑得到的拓扑序就是一个合法的连接顺序。

总结一下算法流程：

用 HK 求最大匹配，时间复杂度 O(n\sqrt n)。

::::info[参考代码]

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,inf=1e9;
vector<int> g[N],G[N];
int dis[N],in[N],n;
struct edge {
    int u,v;
}e[N];
int L[N],R[N];//L[u]左部点u匹配右部分点编号
bool bfs(){
    queue<int> q;
    for(int u=1;u<=n;u++){
        if(!L[u])dis[u]=0,q.push(u);
        else dis[u]=inf;
    }
    bool flag=false;
    while(q.size()){
        int u=q.front();
    //  cout<<"u="<<u<<"\n";
        q.pop();
        for(int id:g[u]){
            int v=R[id];
            if(v==0)flag=true;
            else if(dis[v]==inf){
                dis[v]=dis[u]+1;
                q.push(v);
            } 
        }
    }
    return flag;
}
bool dfs(int u){
    for(int id:g[u]){
        int v=R[id];
        if(v==0||(dis[v]==dis[u]+1&&dfs(v))){
            L[u]=id;R[id]=u;
        //  cout<<"u="<<u<<" v="<<v<<"\n";
            return true;
        }
    }
    dis[u]=inf;
    return false;
}
int dicnic(){
    int res=0;
    while(bfs()){
        for(int i=1;i<=n;i++){
            if(L[i]==0&&dfs(i))res++;
        }
    }
    return res;
}
int pre[N],nxt[N];//原图前驱后继
int id[N];//属于哪条路径
vector<int> st,en,vec;//vec拓扑序
bool vis[N];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n-1;i++){
        cin>>e[i].u>>e[i].v;
        g[e[i].u].push_back(e[i].v);
    }
    int m=dicnic();
    for(int u=1;u<=n;u++){
        if(L[u])nxt[u]=L[u];
    }
    for(int u=1;u<=n;u++){
        if(R[u])pre[u]=R[u];
    }
    memset(id,-1,sizeof id);
    int tot=0;
    for(int u=1;u<=n;u++){
        if(!pre[u]) {
            int now=u;
            st.push_back(u);
            int lst=u;
            while(now&&id[now]==-1){
                id[now]=tot;
                lst=now;
                now=nxt[now];
            }
            en.push_back(lst);
            tot++;
        }
    }
    for(int u=1;u<=n;u++){
        if(id[u]==-1) {
            id[u]=tot;
            st.push_back(u);
            en.push_back(u);
            tot++;
        }
    }
    for(int i=1;i<=n-1;i++){
        int u=id[e[i].u],v=id[e[i].v];
        if(u!=v)G[u].push_back(v);
    }
    for(int i=0;i<tot;i++){
        sort(G[i].begin(),G[i].end());
        G[i].erase(unique(G[i].begin(),G[i].end()),G[i].end());
        for(int v:G[i])in[v]++;
    }
    queue<int> q;
    while(q.size())q.pop();
    for(int i=0; i<tot; i++){
        if(!in[i])q.push(i);
    }
    while(q.size()){
        int u=q.front();
        q.pop();
        vec.push_back(u);
        vis[u]=1;
        for(int v:G[u]){
            in[v]--;
            if(!in[v])q.push(v);
        }
    }
    if(vec.size()<tot){
        for(int i=0;i<tot;i++){
            if(!vis[i])vec.push_back(i);
        }
    }
    vector<edge> ans;
    for(int i=0;i<vec.size()-1;i++)ans.push_back({en[vec[i]],st[vec[i+1]]});
    cout<<ans.size()<<"\n";
    for(auto tmp:ans)cout<<tmp.u<<" "<<tmp.v<<"\n";
    return 0;
}
/*5
1 2
1 3
3 4
3 5*/

::::