最小路径覆盖

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

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

Input

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

Output

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

Example

样例输入

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 4 7 10 11 2 5 8 3 6 9 3

Hint

$1\le n\le 200,1\le m\le 6000$

思路

把原图的每个点 $V$ 拆成 $V_x$和 $V_y$两个点，如果有一条有向边 $A$->$B$，那么就加边 $A_x$−>$B_y$。这样就得到了一个二分图。那么最小路径覆盖=原图的结点数$-$新图的最大匹配数

#include <bits/stdc++.h> using namespace std; const int maxn=1e4+7; const int maxm=2e5+7; const int inf=0x3f3f3f3f; int n,m,u,v; struct Dinic { struct Edge { int next, f, to; } e[maxm]; int head[maxn], dep[maxn], tol, ans; int cur[maxn]; int src, sink, n; void add(int u, int v, int f) { tol++; e[tol].to = v; e[tol].next = head[u]; e[tol].f = f; head[u] = tol; tol++; e[tol].to = u; e[tol].next = head[v]; e[tol].f = 0; head[v] = tol; } bool bfs() { queue<int> q; memset(dep, -1, sizeof(dep)); q.push(src); dep[src] = 0; while (!q.empty()) { int now = q.front(); q.pop(); for (int i = head[now]; i; i = e[i].next) { if (dep[e[i].to] == -1 && e[i].f) { dep[e[i].to] = dep[now] + 1; if (e[i].to == sink) return true; q.push(e[i].to); } } } return false; } int dfs(int x, int maxx) { if (x == sink) return maxx; for (int &i = cur[x]; i; i = e[i].next) { if (dep[e[i].to] == dep[x] + 1 && e[i].f > 0) { int flow = dfs(e[i].to, min(maxx, e[i].f)); if (flow) { e[i].f -= flow; e[i ^ 1].f += flow; return flow; } } } return 0; } int dinic(int s, int t) { ans = 0; this->src = s; this->sink = t; while (bfs()) { for (int i = 0; i <= n; i++) cur[i] = head[i]; while (int d = dfs(src, inf)) ans += d; } return ans; } void init(int n) { this->n = n; memset(head, 0, sizeof(head)); tol = 1; } } G; int pre[maxn],sec[maxn]; template<typename T> inline void read(T &x) { x = 0; static int p; p = 1; static char c; c = getchar(); while (!isdigit(c)) { if (c == '-')p = -1; c = getchar(); } while (isdigit(c)) { x = (x << 1) + (x << 3) + (c - 48); c = getchar(); } x *= p; } template <typename T> inline void print(T x) { if (x<0) { x = -x; putchar('-'); } static int cnt; static int a[50]; cnt = 0; do { a[++cnt] = x % 10; x /= 10; } while (x); for (int i = cnt; i >= 1; i--)putchar(a[i] + '0'); //puts(""); } int isnot_head[maxn],to[maxn]; int main() { read(n); read(m); int S = 0, T = n * 2 + 1; G.init(T); for (int i = 1; i <= m; i++) { read(u); read(v); G.add(u, v + n, 1); } for (int i = 1; i <= n; i++) { G.add(S, i, 1); } for (int i = n + 1; i <= n * 2; i++) { G.add(i, T, 1); } for (int i = 0; i <= T; i++) to[i] = i; int ans = G.dinic(S, T); for (int i = 2; i <= G.tol; i+=2) { int u = G.e[i ^ 1].to; int v = G.e[i].to; if (u != S && v != T && G.e[i ^ 1].f != 0) { v -= n; to[u] = v; isnot_head[v] = 1; } } for (int i = 1; i <= n; i++) { int j = i; if (!isnot_head[j]) { printf("%d ", j); while (to[j] != j) { printf("%d ", to[j]); j = to[j]; } puts(""); } } print(n - ans); puts(""); return 0; }