给定有向图 $G = (V, E)$ 。设 $P$ 是 $G$ 的一个简单路（顶点不相交）的集合。如果 $V$ 中每个顶点恰好在 $P$ 的一条路上，则称 $P$ 是 $G$ 的一个路径覆盖。 $P$ 中路径可以从 $V$ 的任何一个顶点开始，长度也是任意的，特别地，可以为 $0$ 。 $G$ 的最小路径覆盖是 $G$ 的所含路径条数最少的路径覆盖。

设计一个有效算法求一个有向无环图 $G$ 的最小路径覆盖。

题解

关于路径覆盖的定义，这题题面里说的比较好。

路径覆盖就是用若干条路径来覆盖一个DAG上的所有点，但是不同路径上的各个顶点不可以重复特别的，一条路径的长度可以为 $1$ ，也就是一个顶点可以算作一条路径

最小路径覆盖的意义就是最小化路径覆盖集的大小

考虑把一个顶点拆成两个，分属集合 $A$ 以及集合 $B$ ，若原图中有某一条边 $(u, v)$ ,则在网络中建立 $(u \in A, v \in B)$ ，在这个二分图上找最大匹配，最终答案就是原图点数减去最大匹配数。

这样做的道理是什么呢? 考虑路径覆盖的定义，我们每将原图中的一条边 $(u, v)$ 加入路径覆盖的条件是: 保证对于路径覆盖集中的任意其他路径，保证不存在 $s \in V, (u, s)$ ; 这和二分图匹配的定义相似，所以我们拆点做二分图匹配

黄学长这题题解里有句话说的非常好：如果无匹配，显然要 $n$ 条路径才能覆盖所有点，两个点匹配意味着将可以把它们用一条路径覆盖，路径数就可以减 $1$

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <new>
#include <queue>
#include <algorithm>
const int MAXN = 400;
const int MAXM = 6000;
struct Node;
struct Edge;
struct Node {
    Edge *e, *c;
    int level, id;
    bool vis;
} N[MAXN + 5];
struct Edge {
    Node *fr, *to;
    Edge *ne, *rev;
    int cap, flow;
    
    Edge() {}
    Edge(Node *fr, Node *to, int cap) : fr(fr), to(to), ne(fr->e), cap(cap), flow(0) {}
};
inline void addEdge(int fr, int to, int cap) {
    N[fr].e = new Edge(&N[fr], &N[to], cap);
    N[to].e = new Edge(&N[to], &N[fr], 0);
    N[fr].e->rev = N[to].e, N[to].e->rev = N[fr].e;
}
struct Dinic {
    bool makeLevelGraph(Node *s, Node *t, int n) {
        for (int i = 0; i < n; i++) N[i].c = N[i].e, N[i].level = 0;
        std::queue<Node *> q;
        q.push(s);
        s->level = 1;
        while (!q.empty()) {
            Node *v = q.front();
            q.pop();
            for (Edge *e = v->e; e; e = e->ne) {
                if (e->cap > e->flow && !e->to->level) {
                    e->to->level = v->level + 1;
                    if (e->to == t) return true;
                    q.push(e->to);
                }
            }
        }
        return false;
    }
    int findPath(Node *s, Node *t, int limit = INT_MAX) {
        if (s == t) return limit;
        for (Edge *&e = s->c; e; e = e->ne) {
            if (e->cap > e->flow && e->to->level == s->level + 1) {
                int flow = findPath(e->to, t, std::min(e->cap - e->flow, limit));
                if (flow > 0) {
                    e->flow += flow;
                    e->rev->flow -= flow;
                    return flow;
                }
            }
        }
        return 0;
    }
    int operator()(int s, int t, int n) {
        int res = 0;
        while (makeLevelGraph(&N[s], &N[t], n)) {
            int flow;
            if ((flow = findPath(&N[s], &N[t])) > 0) res += flow;
        }
        return res;
    }
} dinic;
void printPath(Node *v) {
    printf("%d ", v->id);
    v->vis = true;
    for (Edge *e = v->e; e; e = e->ne) {
        if (e->flow == e->cap && e->to->id != 0 && !N[e->to->id].vis) {
            printPath(&N[e->to->id]);
            break;
        }
    }
}
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    // let [1, n] equal to the set A, [n + 1, n * 2] equal to the set B;
    const int s = 0, t = n * 2 + 1;
    for (int i = 1; i <= n; i++) addEdge(s, i, 1), addEdge(i + n, t, 1), N[i].id = N[i + n].id = i;
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        addEdge(u, v + n, 1);
    }
    int res = dinic(s, t, n * 2 + 2);
    for (int i = 1; i <= n; i++) {
        if (!N[i].vis) {
            printPath(&N[i]);
            puts("");
        }
    }
    
    printf("%d\n", n - res);
    return 0;
}

「网络流24题」最小路径覆盖

Contents

题解

代码