这个题是一种题型，其实也就是拆一下点。
分析：
我们首先将原图用n条路径覆盖，每条边只经过每个节点。
现在尽量合并更多的路径(即将两个路径通过一条边首尾相连)。
可以知道，每合并两条路径，图中的路径覆盖数就会减少1。
所以我们只需要利用网络流合并相关的路径即可。
答案求解：
首先将每个节点拆成(Xi,Yi)两个节点，建立源点和汇点，分别连接(S,Xi)和(Yi,T)。
然后对于每一条原图中的边，建立边(Xi,Yi)即可。
这样每一条增广路都只会经过2个节点(Xa,Yb)，对应合并的两个节点。
由于每个节点至多与一个节点合并，故边(S,Xi)和(Yi,T)容量为1。
此时的最大流对应的就是最多可以合并的路径数。
方案输出：
由于本人没有想到什么好的输出方法，故只能比较蠢地根据网络流的残余流量构造每一条路径(利用并查集维护路径起点)，然后从起点递归输出。
题干：
题目描述 给定有向图 G=(V,E)G=(V,E)G=(V,E) 。设 PPP 是 GGG 的一个简单路(顶点不相交)的集合。如果 VVV 中每个定点恰好在PPP的一条路上，则称 PPP 是 GGG 的一个路径覆盖。PPP中路径可以从 VVV 的任何一个定点开始，长度也是任意的，特别地，可以为 000 。GGG 的最小路径覆盖是 GGG 所含路径条数最少的路径覆盖。设计一个有效算法求一个 GAP (有向无环图) GGG 的最小路径覆盖。 提示：设 V={1,2,...,n}V={1,2,...,n}V={1,2,...,n} ，构造网络 G1={V1,E1}G_1={V_1,E_1}G1={V1,E1} 如下： V1={x0,x1,...,xn}∪{y0,y1,...,yn}V_1={x_0,x_1,...,x_n}cup{y_0,y_1,...,y_n}V1={x0,x1,...,xn}∪{y0,y1,...,yn} E1={(x0,xi):i∈V}∪{(yi,y0):i∈V}∪{(xi,yj):(i,j)∈E}E_1={(x_0,x_i):iin V}cup{(y_i,y_0):iin V}cup{(x_i,y_j):(i,j)in E}E1={(x0,xi):i∈V}∪{(yi,y0):i∈V}∪{(xi,yj):(i,j)∈E} 每条边的容量均为 111 ，求网络 G1G_1G1 的 (x0,y0)(x_0,y_0)(x0,y0) 最大流。 输入输出格式 输入格式： 第一行有 222 个正整数 nnn 和 mmm 。 nnn 是给定GAP ext{GAP}GAP(有向无环图) GGG 的顶点数， mmm 是 GGG 的边数。接下来的 mmm 行,每行有两个正整数 iii 和 jjj 表示一条有向边 (i,j)(i,j)(i,j)。 输出格式： 从第1 行开始，每行输出一条路径。文件的最后一行是最少路径数。
代码：
#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<queue> #include<algorithm> #include<cstring> using namespace std; #define duke(i,a,n) for(register int i = a;i <= n;++i) #define lv(i,a,n) for(register int i = a;i >= n;--i) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1 << 30; typedef long long ll; typedef double db; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } const int N = 1e5 + 5; struct node { int l,r,nxt,w,oth; }a[N * 10]; int len = 0,lst[N],m; void add(int x,int y,int w) { // cout<<x<<" "<<y<<" "<<w<<endl; int k1,k2; a[++len].l = x; a[len].r = y; a[len].w = w; a[len].nxt = lst[x]; lst[x] = len; k1 = len; a[++len].l = y; a[len].r = x; a[len].w = 0; a[len].nxt = lst[y]; lst[y] = len; k2 = len; a[k1].oth = k2; a[k2].oth = k1; } int n,p,q; int h[N],ed = 0; bool bfs() { clean(h); h[0] = 1; queue <int> q; q.push(0); while(!q.empty()) { int x = q.front(); q.pop(); for(int k = lst[x];k != -1;k = a[k].nxt) { int y = a[k].r; if(a[k].w > 0 && h[y] == 0) { h[y] = h[x] + 1; q.push(y); } } } if(h[ed] > 0) return true; else return false; } int find(int x,int f) { if(x == ed) { return f; } int s = 0,t; for(int k = lst[x];k != -1;k = a[k].nxt) { int y = a[k].r; if(s < f && h[y] == h[x] + 1 && a[k].w > 0) { t = find(y,min(a[k].w,f - s)); s += t; a[k].w -= t; a[a[k].oth].w += t; } } if(s == 0) h[x] = 0; return s; } int fa[N]; int find(int x) { if(fa[x] == x) return x; return fa[x] = find(fa[x]); } void work(int x) { printf("%d ",x); for(int k = lst[x];k != -1;k = a[k].nxt) { int y = a[k].r; if(y > n && a[k].w == 0) work(y - n); } } int main() { read(n);read(m); memset(lst,-1,sizeof(lst)); duke(i,1,n) add(0,i,1); ed = 2 * n + 1; duke(i,1,n) { add(n + i,ed,1); } duke(i,1,m) { int x,y; read(x);read(y); add(x,y + n,1); } int s = 0; while(bfs() == true) { s += find(0,INF); } duke(i,1,n) fa[i] = i; duke(i,1,len) if(a[i].l >= 1 && a[i].l <= n && a[i].r > n && a[i].w < ed && a[i].w == 0) fa[find(a[i].r - n)] = find(a[i].l); duke(i,1,n) { if(fa[i] == i) { work(i); puts(""); } } printf("%d ",n - s); return 0; }