题解：P16106 [ICPC 2019 NAIPC] Planes, Trains, but not Automobiles

· · 题解

题意简述

给定一张表示单向铁路的有向无环图，任意两座城市之间都可以乘飞机。选择起点并恰好访问每座城市一次，求最少乘机次数，以及在某条最优路线中可能作为飞机起点或终点的所有城市。

解题思路

将一条旅行路线中的飞机边删去，剩余部分就是若干条互不相交的铁路路径，恰好覆盖全部城市。反过来，任意一组这样的路径都可以用飞机依次连接。因此，若最少需要 k 条铁路路径覆盖全部城市，答案就是 k-1 次航班。

把每座城市拆成左右两个点，铁路 u\to v 对应二分图中左侧 u 到右侧 v 的边。选择一组匹配，相当于给部分城市选择铁路后继和前驱：每座城市至多有一个后继、至多有一个前驱。原图没有有向环，所以这些边一定组成若干条路径，不会出现环。

初始有 n 条单点路径，每加入一条匹配边就将两条路径连接，因此大小为 M 的匹配对应 n-M 条路径。任何路径覆盖中的全部铁路边也会构成匹配，故最大匹配与最小路径覆盖相互对应。代码使用分层增广求最大匹配，以 l[u] 和 r[v] 分别记录左侧点、右侧点的匹配对象，最终得到 k=n-M。

还需要判断一座城市能否在 某个 最小路径覆盖中成为路径端点，不能仅检查当前匹配得到的端点。

若 k=1，整段旅行不需要乘飞机，第二行必须为空。若 k\ge2，可以自由调整各条路径的连接顺序。任意路径都可以安排在非第一条的位置，也可以安排在非最后一条的位置，因此任意路径起点都能有飞机飞入，任意路径终点都能有飞机飞出。

问题就变成：给定一个最大匹配，找出每侧所有 能在某个最大匹配中不匹配的点。

先处理左侧。从当前所有未匹配左侧点出发，沿「非匹配边走到右侧，再沿匹配边返回左侧」的方式搜索。所有能到达的左侧点，都可以变成未匹配点。

这是因为，从某个未匹配左侧点到目标左侧点的交替路径具有偶数条边，非匹配边与匹配边数量相等。将路径上所有边的选取状态取反，匹配大小不变。原起点得到匹配，目标点失去匹配，仍然得到最大匹配。

这个搜索也不会遗漏答案。设另一个最大匹配使左侧点 u 未匹配，而当前匹配使其匹配。比较两个匹配，仅保留恰好属于其中一个匹配的边，它们会分解成若干交替路径和交替环。包含 u 的分量必然是一条路径。两个匹配都是最大的，所以不可能出现能够使其中一个匹配增广的路径。于是该路径必须以另一个左侧点结束，该点在当前匹配中未匹配；从它出发就能按上述方向走到 u。

处理右侧时交换两侧角色，并沿原二分图边的反方向搜索。两次得到的城市集合取并集，就是全部可能使用机场的城市。

mark(G,l,r) 完成左侧搜索。访问左侧点 u 后，枚举相邻右侧点 v，继续访问其匹配点 r[v]。实现没有专门排除 u 自己的匹配边：沿这条边再返回会回到 u，访问标记会立即跳过，因此不影响可达集合。最大匹配下不可能从未匹配左侧点到达未匹配右侧点，否则产生增广路径。mark(H,r,l) 使用反向邻接表完成右侧搜索。

最大匹配部分的 bfs 记录各个左侧点的层数，以及到达未匹配右侧点的最短层数 dep。dfs 仅沿层数增加的边前进，并且仅在最短层终止增广。cur 保存每个点本轮尚未尝试的边，避免反复扫描失败分支。为了处理长交替路径，st 和 ed 显式保存当前路径，找到终点后倒序改写匹配，不依赖递归深度。

最大匹配的时间复杂度为 O((n+m)\sqrt n)，两次交替搜索为 O(n+m)，空间复杂度为 O(n+m)。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=100005;
int n,dep;
int l[N],r[N],dis[N],cur[N],st[N],ed[N];
bool vis[N],ans[N];
vector<int> G[N],H[N];
bool bfs()
{
    fill(dis,dis+n+1,-1);
    queue<int> q;
    for(int i=1;i<=n;i++)if(!l[i]){dis[i]=0;q.push(i);}
    dep=n+1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        if(dis[u]>=dep)continue;
        for(auto v:G[u])
        {
            if(!r[v])dep=dis[u]+1;
            else if(dis[r[v]]==-1){dis[r[v]]=dis[u]+1;q.push(r[v]);}
        }
    }
    return dep<=n;
}
bool dfs(int u)
{
    int top=1;
    st[top]=u;
    while(top)
    {
        u=st[top];
        if(cur[u]==G[u].size()){dis[u]=-1;top--;continue;}
        int v=G[u][cur[u]++];
        if(!r[v]&&dis[u]+1==dep)
        {
            ed[top]=v;
            for(int i=top;i>=1;i--){l[st[i]]=ed[i];r[ed[i]]=st[i];}
            return 1;
        }
        if(r[v]&&dis[r[v]]==dis[u]+1)
        {
            ed[top]=v;
            top++;
            st[top]=r[v];
        }
    }
    return 0;
}
void mark(vector<int> *G,int *l,int *r)
{
    fill(vis,vis+n+1,0);
    queue<int> q;
    for(int i=1;i<=n;i++)if(!l[i]){vis[i]=1;q.push(i);}
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        ans[u]=1;
        for(auto v:G[u])
        {
            if(r[v]&&!vis[r[v]]){vis[r[v]]=1;q.push(r[v]);}
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        H[v].push_back(u);
    }
    int cnt=n;
    while(bfs())
    {
        fill(cur,cur+n+1,0);
        for(int i=1;i<=n;i++)if(!l[i]&&dfs(i))cnt--;
    }
    cout<<cnt-1<<'\n';
    if(cnt>1)
    {
        mark(G,l,r);
        mark(H,r,l);
        for(int i=1;i<=n;i++)if(ans[i])cout<<i<<' ';
    }
    cout<<'\n';
    return 0;
}