题目地址（关于此题的 SPJ，洛谷上的是没有问题的，LibreOJ上的SPJ是错的，详见：https://loj.ac/article/903）

题意

求一个有向无环图的最小路径覆盖，路径之间不能有相同的点，路径的距离可以为零。

做法&分析

• 用二分图，对于每一个点$i$, 在右边建立点$i + N$
• 对于题目中给的每一条边$(u, v)$, 连接$(u, v + N)$, 边为$1$(其实中间的边权无所谓，设成INF也可以，后面会讲到)
• 连接源点$S$到点$1 - N$, 边权为$1$, 连接点$N + 1 - N + N$到汇点$T$
• 答案为$N - 最大流$

分析一下为什么这么做。

感性理解一下，根据题意，一个有向无环图的任意一个路径覆盖其实是相当于根据边把图中的点合并成若干集合。

那么做法中二分图中间的有向边$(u, v)$就代表把$u$和$v - N$合并，因为在一条路径中每一个点最多只能有一条出边也最多只能有一条入边，所以源点$S$连出去的边和连向汇点$T$的边的边权都为$1$。

而有了源点和汇点所连的边的限制，中间的边边权大于$1$即可。

这样最大流的意义就等同于最多能合并的次数。

求完以后点的集合总数等于$N - 合并次数$。

所以最后的答案$Answer = N - 最大合并次数 = N - 最大流$。

还有一个问题，就是输出最小路径覆盖的方案。

按照以上我讲的理解方式的话就很好输出了。

可以发现这个题比较特殊，即每一条从$S$到$T$的点的容量最多为$1$。

如果你理解Dinic的原理，可以发现每一次dfs中每一个节点的流量只能往外流一次，那么我们记录$1 - N$中的每一个节点的流量流向了对面对应的哪一个点，类似链表，每一条路径组成了一条链。

最后从$N + 1$到$N + N$的所有点中找连向汇点$T$的边的边权仍然为1的点（也就是没有被其他点合并到的点，他们一定是每一条链的开头），从他们开始沿着链输出就好了。

代码

#include 
#include 
#include 
#include 
#define maxN 505
#define maxM 100005
#define INF 2e9
using namespace std;

int N, M, S, T, Cut;

struct Edge {
    int to, nxt, dis;
}e[maxM << 1];

int cnte = 1, head[maxN];

inline void add_Edge(int i, int j, int k) {
    e[++cnte].dis = k, e[cnte].nxt = head[i], e[cnte].to = j, head[i] = cnte;
    e[++cnte].dis = 0, e[cnte].nxt = head[j], e[cnte].to = i, head[j] = cnte;
}

int dep[maxN];
bool bfs() {
    queue <int> Q;
    memset(dep, 0, sizeof(dep));
    dep[S] = 1, Q.push(S);
    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        for(int v, i = head[u]; i; i = e[i].nxt) {
            if(e[i].dis && !dep[v = e[i].to]) {
                dep[v] = dep[u] + 1, Q.push(v);
            }
        }
    }
    return dep[T];
}

int nx[maxN];
bool vis[maxN];
int dfs(int u, int in) {
    if(u == T) return in;
    int out = 0;
    for(int v, i = head[u]; i; i= e[i].nxt) {
        if(e[i].dis && dep[v = e[i].to] == dep[u] + 1) {            
            int tmp = dfs(v, min(in, e[i].dis));
            if(tmp > 0) nx[u] = v - N, vis[v - N] = true;
            e[i].dis -= tmp, e[i ^ 1].dis += tmp;
            in -= tmp, out += tmp;
        }
    }
    if(!out) dep[u] = 0;
    return out;
}

int main() {
    cin >> N >> M;
    S = (N << 1) + 1, T = S + 1;
    for(int u, v, i = 1; i <= M; ++i) {
        cin >> u >> v;
        add_Edge(u, N + v, 1);
    }
    for(int i = 1; i <= N; ++i) 
        add_Edge(S, i, 1), add_Edge(N + i, T, 1);
    while(bfs()) Cut += dfs(S, INF);
    for(int u = N + 1; u <= (N << 1); ++u) {
        if(!e[head[u]].dis) continue;
        int p = u - N;
        cout << p << ' ';
        int i = nx[p];
        while(i > 0) {
            cout << i << ' ';
            i = nx[i];
        }
        cout << '\n';
    }
    cout << N - Cut << '\n';
    return 0;
}