這個題是一種題型，其實也就是拆一下點。
分析：
我們首先将原圖用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;
}