最小路径覆盖问题（最大流，最小路径点覆盖，二分图，网络流24题）

题意

给定有向图 (G=(V,E))。

设 (P) 是 (G) 的一个简单路(顶点不相交)的集合。

如果 (V) 中每个顶点恰好在 (P) 的一条路上，则称 (P) 是 (G) 的一个路径覆盖。

(P) 中路径可以从 (V) 的任何一个顶点开始，长度也是任意的，特别地，可以为 (0)。

(G) 的最小路径覆盖是 (G) 的所含路径条数最少的路径覆盖。

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

思路

最小路径点覆盖问题的一般思路是：设原来的有向无环图为(G = (V, E))，(n = |V|)。把(G)中的每个点(x)拆成编号为(x)和(x+n)的两个点。建立一张新的二分图，(1 sim n)作为二分图左部点，(n + 1 sim 2n)作为二分图右部点，对于原图的每条有向边((x,y))，在二分图的左部点(x)与右部点(y+n)之间连边。最终得到的二分图称为(G)的拆点二分图，记为(G_2)。

定理：有向无环图(G)的最小路径点覆盖包含的路径条数，等于(n)减去拆点二分图(G_2)的最大匹配数。

因此这道题只需要跑一遍二分图匹配即可。

这里的路径输出可以采用这样的方法，遍历二分图中每一条满流的正向弧，这样可以求出每个点的上一个点以及下一点是谁。没有上一个点的点就是起点，没有下一个点的点就是终点。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 310, M = (6000 + 310 * 2) * 2 + 10, inf = 1e8;

int n, m, S, T;
int h[N], e[M], ne[M], f[M], idx;
int cur[N], d[N];
int sec[N], pre[N];

void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}

bool bfs()
{
    memset(d, -1, sizeof(d));
    queue<int> que;
    que.push(S);
    d[S] = 0, cur[S] = h[S];
    while(que.size()) {
        int t = que.front();
        que.pop();
        for(int i = h[t]; ~i; i = ne[i]) {
            int ver = e[i];
            if(d[ver] == -1 && f[i]) {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if(ver == T) return true;
                que.push(ver);
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = ne[i]) {
        cur[u] = i;
        int ver = e[i];
        if(d[ver] == d[u] + 1 && f[i]) {
            int t = find(ver, min(f[i], limit - flow));
            if(!t) d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}


int dinic()
{
    int res = 0, flow;
    while(bfs()) {
        while(flow = find(S, inf)) {
            res += flow;
        }
    }
    return res;
}

void get()
{
    for(int i = 0; i < 2 * m; i += 2) {
        if(!f[i]) {
            int b = e[i], a = e[i ^ 1];
            pre[b - n] = a;
            sec[a] = b - n;
        }
    }
}

void output(int u)
{
    printf("%d", u);
    while(sec[u]) {
        printf(" %d", sec[u]);
        u = sec[u];
    }
    puts("");
}

int main()
{
    scanf("%d%d", &n, &m);
    S = 0, T = 2 * n + 1;
    memset(h, -1, sizeof(h));
    for(int i = 0; i < m; i ++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b + n, 1);
    }
    for(int i = 1; i <= n; i ++) {
        add(S, i, 1);
        add(n + i, T, 1);
    }
    int res = dinic();
    get();
    for(int i = 1; i <= n; i ++) {
        if(!pre[i]) {
            output(i);
        }
    }
    printf("%d
", n - res);
    return 0;
}