P2764 最小路径覆盖问题

一条匹配边会把两条路径接成一条

问题

P2764 最小路径覆盖问题
给定一个 DAG，要求用若干条点不相交的有向路径覆盖每个顶点恰好一次，并使路径数量最少。单独一个顶点也可以作为一条路径，同时要求输出一种最优方案。

数据规模：$1\le n\le150$，$1\le m\le6000$。

最开始可以先把每个顶点都独立看作一条路径，此时一共有 $n$ 条路径，如果选择原图中的一条边 $u \to v$ 并且让 $v$ 成为 $u$ 路径的后继，就可以把原本两条路径合并，使路径数量减少 $1$。

于是问题就可以转化为：最多同时选择多少条原图上的边，将路径合并。

接着我们考虑如何把两个点所代表的路径合并 —— 一条合法路径中，每个顶点至多选择一个后继，也至多被一个前驱选择。

于是把每个原图顶点 $u$ 复制成左部点 $u_L$ 与右部点 $u_R$，分别表示“作为前驱”和“作为后继”两个角色；若原图存在 $u\to v$，就在二分图中连接 $u_L\to v_R$。

左部点至多匹配一次，限制一个顶点最多拥有一个后继；右部点至多匹配一次，限制一个顶点最多拥有一个前驱。因此一组匹配边正好对应一组可以同时存在的路径相邻关系。

本题的角色复制和 P1231 教辅的组成 中的容量拆点需要区分。P1231 是为了限制节点本身的总通过量，而本题是把同一个顶点“作为前驱”和“作为后继”两个角色分别表示。

于是答案就是 $n - M$，每选择一条匹配边，就会把两条路径连接为一条，因此路径数量减少 $1$，若最大匹配大小为 $M$，那么最小路径覆盖数就是 $n - M$。

注：本题的 DAG 条件也很重要，它能保证被选出的后继关系不会形成有向环。

输出方案只需要在最大流结束后，对于每条原图中对应的正向边，判断 $u_{L} \to v_{R}$ 的原始容量是否从 $1$ 变成 $0$。

▶

AC 建图与恢复

namespace DINIC { /* 模板代码略 */ }
using namespace DINIC;

struct Path { int u, v, id; };
int pre[maxn], nxt[maxn];

void solve( ) {
    int n = read( ), m = read( );
    vector<int> ai( n + 1 ), ao( n + 1 );

    int tot = 0;
    for( int i = 1; i <= n; ++ i ) ai[i] = ++ tot;
    for( int i = 1; i <= n; ++ i ) ao[i] = ++ tot;

    int S = ++ tot, T = ++ tot;
    init( tot );

    for( int i = 1; i <= n; ++ i ) {
        add_edge( S, ai[i], 1 );
        // add_edge( ai[i], ao[i], 1 ); 这条是错误的！
        add_edge( ao[i], T, 1 );
    }

    vector<Path> paths;
    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( );
        paths.push_back({ u, v, (int)edge.size( ) });
        add_edge( ai[u], ao[v], 1 );
    }

    ll mxflow = Dinic( S, T, tot );
    
    for( auto [u, v, id] : paths ) {
        if( edge[id].c == 0 ) {
            pre[v] = u, nxt[u] = v;
        }
    }

    for( int i = 1; i <= n; ++ i ) {
        if( pre[i] ) continue;
        int u = i;
        while( u ) {
            cout << u << " ";
            u = nxt[u];
        }
        cout << '\n';
    }

    cout << n - mxflow << '\n';
}