题目解析

完整的解析与思维过程,参考本仓库的目录 problems/luogu/2664/_DAG 最小路径覆盖解析.md

图论详解：DAG 最小路径覆盖问题的网络流解法

在图论问题中，最小路径覆盖（Minimum Path Cover）是一个非常经典的模型。它通常出现在二分图匹配或网络流的练习题中（例如 P2764）。

很多同学初学时虽然能背下公式，但往往对“为什么要拆点”、“为什么要用二分图匹配”以及“最大匹配数和最长链的区别”感到困惑。

本文将剥离复杂的代码实现，通过图解和逻辑推导，带你彻底理解这个问题背后的数学直觉。

1. 问题定义

给定一个 有向无环图 (DAG) $G=(V,E)$ 。我们需要找出最少数量的路径，使得图中的每一个顶点都恰好属于其中的一条路径（顶点不相交）。

路径长度不限，可以是单独一个点（长度为0）。

举个栗子： 假设 DAG 为 $1 \to 2$ 和 $3 \to 4$ （两段互不相连的线段）。那么最小路径覆盖就是 2 条： $\{1 \to 2\}$ 和 $\{3 \to 4\}$ 。

2. 核心公式

解决这个问题的金科玉律是：

\text{最小路径覆盖数} = \text{顶点总数 } (n) - \text{最大二分匹配数}

或者在网络流语境下：

\text{最小路径覆盖数} = n - \text{最大流 (Max Flow)}

看到这个公式，我们自然会产生三个疑问：

这个二分图是怎么建出来的？
为什么减去匹配数就是路径数？
最大匹配数等于图上的最长链吗？

我们一一解答。

3. 建模方法：拆点法

在一个 DAG 中，每个节点 $u$ 其实有两个“身份”：

作为起点的身份：它可能指向别人（例如 $u \to v$ ）。
作为终点的身份：它可能被别人指向（例如 $k \to u$ ）。

为了在网络流/二分图中体现这两个身份的互斥性，我们使用拆点法：将原图中的每一个点 $i$ 拆成两个点：左部点 $X_i$ 和 右部点 $Y_i$ 。

建图步骤（网络流版）：

设立源汇：建立源点 $S$ 和汇点 $T$ 。
限制出度：从 $S$ 向所有的左部点 $X_i$ 连边，容量为 1。
- 含义：点 $i$ 作为路径的前驱，只能使用一次。
限制入度：从所有的右部点 $Y_i$ 向 $T$ 连边，容量为 1。
- 含义：点 $i$ 作为路径的后继，只能被使用一次。
连接原图边：如果原图中有边 $u \to v$ ，则连接 $X_u \to Y_v$ ，容量为 1。
- 含义：尝试把 $u$ 和 $v$ 拼接在一起，u 做头，v 做尾。

4. 深度解析：为什么这样转化？

这是理解本题最关键的一步。

最小路径覆盖的本质，其实是一场“积木拼接游戏”。

最开始，图上有 $n$ 个点，它们都是孤立的。此时我们有 $n$ 条路径（每个点自成一条路径）。
我们的目标是让路径数量变少。怎么变少呢？
每当我们把两个点“拼”在一起（比如把 $u$ 和 $v$ 连成 $u \to v$ ），原本两条独立的路径就合并成了一条。
每成功拼接一次，总路径数就减少 1。

“路径性质”与“匹配限制”的完美对应

为什么可以用二分图匹配来做拼接？因为二分图匹配的规则完美复现了简单路径的约束：

路径的约束 (原图)	二分图匹配的约束 (新图)
一个点只能走向一个点 (不能 $1\to2$ 且 $1\to3$ )	左部点 $X$ 出度限 1 $X_1$ 只能匹配一条边，要么连 $Y_2$ ，要么连 $Y_3$ 。
一个点只能被一个点连接 (不能 $1\to3$ 且 $4\to3$ )	右部点 $Y$ 入度限 1 $Y_3$ 只能接受一条边，要么来自 $X_1$ ，要么来自 $X_4$ 。

因此，求最大流（最大匹配），就是在求**“全图最多能进行多少次合法的拼接”**。

拼接次数越多，剩下的独立路径就越少。所以： $\text{路径数} = \text{初始点数} - \text{拼接次数 (Max Flow)}$ 。

5. 常见误区：最大匹配 = 最长链？

很多同学会误以为最大匹配数就是 DAG 上最长那条链的长度。 这是错误的。

反例： 考虑图： $1 \to 2$ 和 $3 \to 4$ 。

最长链：长度为 1（只有一条边）。
最大匹配：2（我们可以选 $X_1 \to Y_2$ 和 $X_3 \to Y_4$ ）。

结论：

最长链关注的是局部（单条路径的最长延伸）。
最大匹配关注的是全局（整个图一共能连多少条边）。只有当最小路径覆盖数为 1 时，两者才在数值上相等。

6. 路径还原 (Output)

求出最小路径数只是第一步，题目通常要求输出具体路径。我们可以在跑完网络流（Dinic/匈牙利）后，检查残量网络。

寻找匹配边：遍历所有 $X_u \to Y_v$ 的边。如果该边的容量变为了 0（或者反向边有流量），说明这条边被选中了。
- 记录 next_node[u] = v。
- 同时标记 has_incoming[v] = true（说明 v 不是龙头）。
寻找路径头：遍历 $1 \dots n$ ，所有 has_incoming[i] == false 的点，就是一条路径的起点。
打印：从起点开始，顺着 next_node 数组递归输出，直到没有后继。

7. 总结

DAG 最小路径覆盖问题的解题模板如下：

拆点： $1 \dots n$ 为左部， $n+1 \dots 2n$ 为右部。
连边：
- $S \to X_i$
- $Y_i \to T$
- 若 $u \to v$ ，则 $X_u \to Y_{v}$
跑最大流：得到 max_flow。
计算答案： $ans = n - max\_flow$ 。
还原路径：利用残量网络构建链表。

这个问题完美展示了如何将几何/拓扑约束（路径不可分叉）转化为代数/流量约束（容量为1），是网络流建模思想的极佳入门案例。

代码

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2025-12-26 15:56:54
 */
#include <bits/stdc++.h>
using namespace std;

// 定义最大点数和边数
// N <= 150，拆点后点数约为 300，加上源汇点。2005 足够。
const int maxn = 2005; 
// M <= 6000，加上源点到X、Y到汇点的边，以及反向边。200005 足够。
const int maxe = 200005; 
const long long INF = 1e18;

// 路径还原辅助数组
// nxt[u] = v 表示在路径覆盖中，点 u 的下一个点是 v
int nxt[maxn]; 
// has_in[v] = true 表示点 v 在路径中作为了某个点的后继（即有入度）
// 用于寻找路径的起点（起点是没有入度的）
bool has_in[maxn];

// 递归打印路径
// 顺着 nxt 数组链表式输出
void print_path(int u) {
    cout << u << " ";
    if (nxt[u] != 0) {
        print_path(nxt[u]);
    }
}

// 链式前向星存图模板
struct linkList {
    // 边结构体：u起点, v终点, w容量, next下一条边索引
    typedef struct {int u,v,w,next;} edge;
    edge e[maxe];
    int h[maxn], edge_cnt=0; // h数组存储每个点的第一条边索引

    // 构造函数：初始化头指针数组为 -1
    linkList(){
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }

    // 遍历辅助函数：遍历点 u 的所有出边
    // 使用模板支持传入 lambda 表达式
    template<typename U>
    void for_each(int u,U func){
        for(int i = h[u] ; i !=-1;i = e[i].next)
            func(e[i].u,e[i].v,e[i].w); // 回调函数参数：u, v, w
    }

    // 添加单向边
    void add(int u,int v,int w=0){
        e[edge_cnt] = {u,v,w,h[u]}; // 头插法
        h[u] = edge_cnt++;
    }
    // 添加双向边（本题未使用）
    void add2(int u,int v,int w=0){
        add(u,v,w);
        add(v,u,w);
    }
    // 重载 [] 方便直接访问边数组
    edge& operator[](int i){ return e[i]; }
    // 重载 () 方便获取 head[u]
    int operator()(int u){ return h[u]; }
} e; // 全局变量 e，存储图数据


// Dinic算法最大流模板 - 基于全局变量 e (linkList) 存图
struct Dinic {
    vector<int> level, iter;  // level: BFS分层图深度, iter: 当前弧优化游标
    int n;  // 总节点数
    
    // 初始化
    Dinic(int n) : n(n), level(n+5), iter(n+5) {
        // 注意：这里重置了全局的 linkList e
        // 如果有多次最大流计算，需注意 clear 问题
        e.edge_cnt = 0;
        memset(e.h, -1, sizeof(e.h));
    }
    
    // 添加网络流的边：包含正向边和反向边
    // u -> v 容量 cap
    // v -> u 容量 0
    void addEdge(int u, int v, long long cap) {
        e.add(u, v, cap);    // 索引 k (偶数)
        e.add(v, u, 0);      // 索引 k+1 (奇数)，互为反向边
    }
    
    // BFS 构建分层图 (Level Graph)
    // 目的：给每个点标号层级，限制 DFS 只能从低层流向高层，防止环流
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            // 遍历 u 的所有邻接边
            e.for_each(u, [&](int from, int to, int cap) {
                // 如果边有残量 (cap > 0) 且终点未被分层
                if (cap > 0 && level[to] < 0) {
                    level[to] = level[u] + 1;
                    q.push(to);
                }
            });
        }
        
        return level[t] >= 0;  // 如果汇点 t 被分层了，说明存在增广路
    }
    
    // DFS 在分层图上寻找增广路 (多路增广)
    // u: 当前点, t: 汇点, preFlow:以此路径到达 u 的最大限制流量
    long long dfs(int u, int t, long long preFlow) {
        if (u == t || preFlow == 0) return preFlow;
        long long flow = 0; // 实际从 u 推送出去的流量
        
        // 当前弧优化：iter[u] 记录点 u 上次处理到的边
        // 避免重复遍历已经流满的废边
        for (int& cid = iter[u]; cid != -1; cid = e[cid].next) {
            auto& edge = e[cid]; 
            int to = edge.v;
            long long cap = edge.w;
            
            // 必须满足层级关系 level[v] = level[u] + 1 且有残量
            if (level[u] + 1 != level[to] || cap <= 0) continue;
            
            // 递归查找后续路径的瓶颈流量
            long long tr = dfs(to, t, min(preFlow, cap));

            // 更新残量网络
            e[cid].w -= tr;       // 正向边容量减少
            e[cid ^ 1].w += tr;   // 反向边容量增加（利用异或1找到反向边）
            flow += tr;
            preFlow -= tr; // 剩余可分配流量减少
            
            if (preFlow == 0) break; // 如果流量分发完了，就结束循环
        }
        
        // 炸点优化 (Gap 优化的一种变体)
        // 如果从 u 出发流不出任何流量，说明 u 实际上已经废弃，从分层图中移除
        if (flow == 0) level[u] = -1;
        return flow;
    }
    
    // Dinic 主过程：求从 s 到 t 的最大流
    long long maxFlow(int s, int t) {
        long long flow = 0;
        // 只要能构建分层图（即存在增广路），就一直增广
        while (bfs(s, t)) {  
            // 每次 BFS 后，重置当前弧 iter 指向每个点的第一条边
            for (int i = 0; i <= n; i++) {
                iter[i] = e(i);  
            }
            
            // 多路增广，初始推入无穷大流量
            flow += dfs(s, t, LLONG_MAX);
        }
        return flow;
    }
};

int main() {
    // 优化输入输出效率
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n, m;  // n个节点，m条边
    int s, t;  // 源点，汇点
    std::cin >> n >> m;
    
    // 设置源点为 0，汇点为 2*n+1
    // 拆点方案：点 i 拆为左部点 i 和 右部点 i+n
    s = 0;
    t = 2 * n + 1;
    
    Dinic dinic(t + 1);  // 创建 Dinic 实例，节点总数需包含汇点
    
    // 1. 构建原图的边 (对应二分图匹配边)
    // 原图 u -> v，在二分图中连线 左部u -> 右部v+n
    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;
        dinic.addEdge(u, v + n, 1);  
    }

    // 2. 构建源点到左部点的边 (限制每个点作为路径起点/中间点流出 1 次)
    for(int i = 1; i <= n; ++i) 
        dinic.addEdge(s, i, 1);

    // 3. 构建右部点到汇点的边 (限制每个点作为路径终点/中间点流入 1 次)
    for(int i = 1; i <= n; ++i) 
        dinic.addEdge(n + i, t, 1);

    // 4. 计算最大二分匹配数 (即最大流)
    auto flow = dinic.maxFlow(s, t);

    // 5. 还原路径
    // 初始化辅助数组
    memset(nxt, 0, sizeof(nxt));
    memset(has_in, 0, sizeof(has_in));

    // 遍历所有左部点 u (1..n)
    for(int u = 1; u <= n; ++u) 
    {
        // 遍历 u 的所有出边
        for(int i = e.h[u]; ~i; i = e[i].next) {
            int v = e[i].v;
            // 判断是否是匹配边：
            // 1. 终点 v 在右部点范围内 (n < v < t)
            // 2. e[i].w == 0 表示容量被用尽，即流量走了这条边 (匹配成功)
            if(v > n && v < t && e[i].w == 0) {
                int real_v = v - n; // 还原出实际点编号
                nxt[u] = real_v;    // 记录路径关系 u -> real_v
                has_in[real_v] = 1; // 标记 real_v 有入度（不是路径头）
                break; // 每个点出度最多为1，找到即可跳出
            }
        }
    }

    // 6. 输出路径
    // 遍历所有点，只要它没有入度 (has_in 为 false)，说明它是一条新路径的起点
    for (int i = 1; i <= n; i++) {
        if (!has_in[i]) {
            print_path(i); // 递归打印整条路径
            cout << endl;
        }
    }

    // 7. 输出最小路径数
    // 最小路径覆盖 = 顶点数 - 最大匹配数 (最大流)
    std::cout << n - flow << "\n";
    
    return 0;
}