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

hzx202303 · 2026-11-11 20:43:20 · 题解

核心判断：一个 DAG 存在唯一的拓扑序当且仅当存在一条经过所有节点的有向哈密顿路径。

::::info[哈密顿路径的定义以及这条结论的证明] 哈密顿路径：一条经过每个点恰好一次的路径。

充分性：

假设这个唯一的拓扑序是 v_1,v_2,\cdots ,v_n，那么每个相邻的节点 v_i,v_{i+1} 之间必有一条有向边。因为假设不存在边 v_i \to v_{i+1}，那么因为它们在拓扑序中相邻，所以两者之间不存在其他有向路径，那么交换它们一定可以构造出另一个拓扑序与唯一拓扑序矛盾了。

所以有唯一的拓扑序 v_1,v_2,\cdots ,v_n，就一定存在一条哈密顿路径 v_1 \to v_2 \to \cdots \to v_n。

必要性：

假设存在 v_1 \to v_2 \to \cdots \to v_n 这条哈密顿路径，根据每条边限制在拓扑序中起点必须出现在终点之前，那么有且仅有 v_1,v_2,\cdots ,v_n 这一个合法拓扑序。

定义一条经过若干节点的有向路径是链。

那么经过所有节点的有向哈密顿路径可以由多条链加上一些边超级拼装出来，所以这就启示我们先跑一遍最小链覆盖后将这些链连接起来。因此第一问的答案的下届就是最小链覆盖数 -1。

但是构造方案时链与链之间不能随便连接，假如存在一条边连接链 L_1,L_2 即 L_1 \to L_2，那么我们不能先连接 L_2 再连接 L_1 否则会形成环。

按照上面的情况我们把链当作节点，连接不同链的边保留就弄出来一个 DAG（原无向图保证是棵树，所以保留下来的边不可能有环），然后我们跑拓扑排序顺着拓扑序连边就做完了。时间复杂度 O(n \sqrt n)，即求最小链覆盖的时间复杂度。

::::info[最小链覆盖的 dinic 实现] 叠甲说明：作者太菜了不会 Hopcroft-Karp，所以我是用 dinic 算法实现的。

最小链覆盖数 = 总点数 N - 二分图最大匹配数。

构造如下：

因为一条链中的节点最多一个前驱和一个后继，所以我们构造二分图来保证：

1. 每个左部点最多匹配一次来选择至多一个后继。
2. 每个右部点最多匹配一次来选择至多一个前驱。

因此定义左部点 L_u 表示以 u 为结尾的链，R_u 表示以 u 为开头的链。

所以对于每一个原图中的有向边 u \to v，连边 L_u \to R_u 表示可以选择这条边将以 u 为结尾的链和以 v 为开头的链拼接起来。

怎么还原链：

定义 L_u 为左部点 u 匹配的右部点，R_u 为右部点 u 匹配的左部点。

::::success[code（dinic 算法）]

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define FOR(i,a,b) for(int i=(a);i<=(int)b;i++)
#define ROF(i,a,b) for(int i=(b);i>=(int)a;i--)
const int N=2e5+10;
const ll inf=1e18+10;
const ll mod=1e9+7;
const double eps=1e-7;
using Vl=vector<int>;
using PI=array<ll,2>;
int n,S,T,h[N<<1],now[N<<1],dep[N<<1],cte=1,q[N<<1],eu[N],ev[N],bl[N],L[N],R[N],st[N],ed[N],in[N],eid[N];
struct E{int v,nxt,w;}e[N*6];
inline int Ae(int u,int v,int w){e[++cte]={v,h[u],w};return h[u]=cte;}
inline bool bfs(){
    fill(dep,dep+T+1,mod);
    int l=1,r=0;dep[q[++r]=S]=0;now[S]=h[S];
    while(l<=r){
        int u=q[l++];
        for(int i=h[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(e[i].w&&dep[v]==mod){
                now[v]=h[v];dep[q[++r]=v]=dep[u]+1;
                if(v==T) return 1;
            }
        }
    }return 0;
}
inline int dfs(int u,int res){
    if(u==T) return res;
    int ct=0;
    for(int &i=now[u],v;i;i=e[i].nxt) if(e[i].w&&(dep[v=e[i].v]==dep[u]+1)){
        int k=dfs(v,min(e[i].w,res));
        if(!k) dep[v]=mod;
        e[i].w-=k,e[i^1].w+=k,ct+=k,res-=k;
        if(!res) break;
    }return ct;
}
Vl g[N];
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
//  ios::sync_with_stdio(0);
//  cin.tie(0);cout.tie(0);
    cin>>n;
    FOR(i,1,n-1) cin>>eu[i]>>ev[i];
    S=0,T=2*n+1;
    FOR(i,1,n) Ae(S,i,1),Ae(i,S,0),Ae(i+n,T,1),Ae(T,i+n,0);
    FOR(i,1,n-1) eid[i]=Ae(eu[i],ev[i]+n,1),Ae(ev[i]+n,eu[i],0);// 建边:以 u 结尾的链 和 以 v 开头的链 链接起来
    while(bfs()) dfs(S,mod);
    FOR(i,1,n-1) if(!e[eid[i]].w) L[eu[i]]=ev[i],R[ev[i]]=eu[i];// L[u] 左部点 u 匹配的右部点，R[u] 右部点 u 匹配的左部点
    int ct=0;
    FOR(i,1,n) if(!R[i]){//一个链的开头
        st[++ct]=i;int u=i;
        while(u) ed[bl[u]=ct]=u,u=L[u];
    }
    FOR(i,1,n-1){
        int u=bl[eu[i]],v=bl[ev[i]];
        if(u^v) g[u].push_back(v),++in[v];
    }
    int l=1,r=0;
    FOR(i,1,ct) if(!in[i]) q[++r]=i;
    Vl dfn;
    while(l<=r){
        int u=q[l++];dfn.push_back(u);
        for(int v:g[u]) if(!--in[v]) q[++r]=v;
    } 
    cout<<--ct<<'\n';
    FOR(i,1,ct) cout<<ed[dfn[i-1]]<<' '<<st[dfn[i]]<<'\n'; 
    return 0;
}

::::