【模板】P2764 最小路径覆盖问题

洛谷P2764 最小路径覆盖问题

题目描述

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

输入格式

第一行有两个正整数 $n$ 和 $m$。$n$ 是给定 DAG（有向无环图）$G$ 的顶点数，$m$ 是 $G$ 的边数。接下来的 $m$ 行，每行有两个正整数 $i$ 和 $j$ 表示一条有向边 $(i,j)$。

输出格式

从第一行开始，每行输出一条路径。文件的最后一行是最少路径数。

输入输出样例 #1

输入 #1

11 12
1 2
1 3
1 4
2 5
3 6
4 7
5 8
6 9
7 10
8 11
9 11
10 11

输出 #1

1 4 7 10 11
2 5 8
3 6 9
3

说明/提示

对于 $100\%$ 的数据，$1\le n\le 150$，$1\le m\le 6000$。

思路:

(虽然是个紫题但是很模板，难度不高)

将每个点$i$拆成两个点 $u_i$,$v_i$，分别是出点和入点，原边$i\to j$变为$u_i\to v_j$
（建图时源点$s$连所有的$u$，汇点$t$连所有的$v$，如图）

这么做可以将图变为二分图，然后最小路径数=节点数量-最大匹配数。

不太严谨的证明如下：

我们首先将原图用n条路径覆盖，每条路径只经过一个节点。
现在尽量合并更多的路径(即将两个路径通过一条边首尾相连，对应二分图中的一条边)。
可以知道，每合并两条路径，图中的路径覆盖数就会减少1。
所以我们只需要合并尽可能多的路径即可。
这一步骤可以通过跑最大流或者直接二分图最大匹配实现。

代码1（匈牙利算法 二分图最大匹配）：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int, int>
#define FU(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, a, b) for (int i = (a); i >= (b); --i)
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 5e5 + 5;

// vector<vector<int>> a(155,vector<int>(155));
vector<int> a[155];
vector<int> p(155), rp(155);
int vis[155];
bool dfs(int x) {
    for (int e : a[x]) {
        if (!vis[e]) {
            vis[e] = true;
            if (rp[e] == 0 || dfs(rp[e])) {
                p[x] = e;
                rp[e] = x;
                return true;
            }
        }
    }
    return false;
}

signed main() {
#ifdef ONLINE_JUDGE
#else
    freopen("../in.txt", "r", stdin);
#endif
    cin.tie(0)->ios::sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        a[u].pb(v);
    }
    for (int i = 1; i <= n; i++) {
        memset(vis, false, sizeof(vis));
        dfs(i);
    }
    
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (rp[i] == 0) {
            ans++;
            int j = i;
            while (j != 0) {
                cout << j << " ";
                j = p[j];
            }
            cout << endl;
        }
    }
    cout << ans;
    return 0;
}

代码2 （Dinic网络最大流）：

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

const int maxn = 100000 + 10;
const int inf = 1 << 30;
struct edge {
    int from, to, cap, flow;
    edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};
struct Dinic {
    int n, m, s, t;
    vector<edge> edges; // 边数的两倍
    vector<int> G[maxn]; // 邻接表，G[i][j]表示结点i的第j条边在e数组中的序号
    bool vis[maxn]; // BFS使用
    int d[maxn];    // 从起点到i的距离
    int cur[maxn];  // 当前弧指针
    void init(int n) {
        this->n = n;
        for (int i = 0; i < n; i++)
            G[i].clear();
        edges.clear();
    }
    void clear() {
        for (int i = 0; i < edges.size(); i++)
            edges[i].flow = 0;
    }
    void reduce() {
        for (int i = 0; i < edges.size(); i++)
            edges[i].cap -= edges[i].flow;
    }
    void addedge(int from, int to, int cap) {
        edges.push_back(edge(from, to, cap, 0));
        edges.push_back(edge(to, from, 0, 0));
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }
    bool BFS() {
        memset(vis, 0, sizeof(vis));
        queue<int> Q;
        Q.push(s);
        vis[s] = 1;
        d[s] = 0;
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            for (int i = 0; i < G[x].size(); i++) {
                edge &e = edges[G[x][i]];
                if (!vis[e.to] && e.cap > e.flow) {
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x, int a) {
        if (x == t || a == 0)
            return a;
        int flow = 0, f;
        for (int &i = cur[x]; i < G[x].size(); i++) {
            edge &e = edges[G[x][i]];
            if (d[x] + 1 == d[e.to] &&
                (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
                e.flow += f;
                edges[G[x][i] ^ 1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0)
                    break;
            }
        }
        return flow;
    }
    int Maxflow(int s, int t) {
        this->s = s;
        this->t = t;
        int flow = 0;
        while (BFS()) {
            memset(cur, 0, sizeof(cur));
            flow += DFS(s, inf);
        }
        return flow;
    }
    vector<vector<int>> getPaths(int N) { // N为原始的节点数量，标号1-N
        vector<vector<int>> paths;
        vector<int> next(N + 1, -1);
        vector<bool> is_start(N + 1, true); // 判断是否为起点

        // Step 1: 找出有流量的中间边，构建后继关系
        for (int u = 1; u <= N; ++u) {
            for (int id : G[2 * u]) {         // 遍历u的出点
                edge &e = edges[id];          // 从u出发的边
                if (e.flow != 1 || e.to == t) // 找出有流量的中间边
                    continue;
                int v = edges[id].to / 2; // 下一个节点原始的v
                next[u] = v;
                is_start[v] = false; // 有前驱的节点标记为非起点
            }
        }

        // Step 2: 从起点开始，收集路径
        for (int u = 1; u <= N; ++u) {
            if (is_start[u]) {
                vector<int> path;
                int now = u;
                while (now != -1) {
                    path.push_back(now);
                    now = next[now];
                }
                paths.push_back(path);
            }
        }
        return paths;
    }
} dinic;

signed main() {
#ifdef ONLINE_JUDGE
#else
    freopen("../in.txt", "r", stdin);
#endif
    cin.tie(0)->ios::sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    int s = 0, t = 1;
    dinic.init(2 * n + 1);
    for (int i = 1; i <= n; i++) {
        int u = i * 2, v = i * 2 + 1;
        dinic.addedge(s, u, 1);
        dinic.addedge(v, t, 1);
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        dinic.addedge(2 * u, 2 * v + 1, 1);
    }
    int ans = dinic.Maxflow(s, t);
    vector<vector<int>> paths = dinic.getPaths(n);
    for (auto &path : paths) {
        for (int node : path)
            cout << node << " ";
        cout << endl;
    }

    cout << n - ans << endl;
    return 0;
}