Description
给定有向图G=(V,E)。设P 是G 的一个简单路（顶点不相交）的集合。如果V 中每个 顶点恰好在P 的一条路上，则称P是G 的一个路径覆盖。P 中路径可以从V 的任何一个顶 点开始，长度也是任意的，特别地，可以为0。G 的最小路径覆盖是G 的所含路径条数最少 的路径覆盖。 设计一个有效算法求一个有向无环图G 的最小路径覆盖。 提示：设V={1，2，... ，n}，构造网络G1=(V1,E1)如下：
每条边的容量均为1。求网络G1的（ x0 , y0 ）最大流。 编程任务： 对于给定的有向无环图G，编程找出G的一个最小路径覆盖。
Input
由文件input.txt提供输入数据。文件第1 行有2个正整数n和m。n是给定有向无环图 G 的顶点数，m是G 的边数。接下来的m行，每行有2 个正整数i和j，表示一条有向边(i,j)。
Output
程序运行结束时，将最小路径覆盖输出到文件output.txt 中。从第1 行开始，每行输出 一条路径。文件的最后一行是最少路径数。
Sample Input
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
Sample Output
1 4 7 10 11 2 5 8 3 6 9 3
题解：
每一个点拆成i和i+n两个，每一个表示他在边中是前驱还是后继，然后所有的前驱init（S，i，1）所有的后继（i+n，T，1）
每一条边（u，v）改成u的前驱到v的后继有一条（u，v+n，INF）的边
然后答案为n-最大流
然后输出路径，已知路径的开始一定后继没有被访问过，所以i+n到T的边依旧为1，可以找出所有路径的开始节点。
然后就是判断他和哪些边匹配过,不断递归输出.
细节很巧妙，详情看代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=,M=,INF=;
int gi(){
int str=;char ch=getchar();
while(ch>'' || ch<'')ch=getchar();
while(ch>='' && ch<='')str=str*+ch-'',ch=getchar();
return str;
}
int n,m,num=,head[N],S=,T,d[N];
struct Lin{
int next,to,dis;
}a[M];
void init(int x,int y,int z){
a[++num].next=head[x];
a[num].to=y;
a[num].dis=z;
head[x]=num;
a[++num].next=head[y];
a[num].to=x;
a[num].dis=;
head[y]=num;
}
int q[N],dep[N];
bool bfs()
{
memset(dep,,sizeof(dep));
q[]=S;dep[S]=;
int x,u,t=,sum=;
while(t!=sum)
{
x=q[++t];
for(int i=head[x];i;i=a[i].next){
u=a[i].to;
if(dep[u] || a[i].dis<=)continue;
dep[u]=dep[x]+;q[++sum]=u;
}
}
return dep[T];
}
int dfs(int x,int flow)
{
if(T==x || !flow)return flow;
int u,tmp,tot=;
for(int i=head[x];i;i=a[i].next){
u=a[i].to;
if(dep[u]!=dep[x]+ || a[i].dis<=)continue;
tmp=dfs(u,min(a[i].dis,flow));
tot+=tmp;flow-=tmp;
a[i].dis-=tmp;a[i^].dis+=tmp;
if(!flow)break;
}
return tot;
}
int maxflow()
{
int tmp,tot=;
while(bfs()){
tmp=dfs(S,INF);
while(tmp)tot+=tmp,tmp=dfs(S,INF);
}
return tot;
}
void hfs(){
int u;
for(int i=head[T];i;i=a[i].next){
if(!a[i].dis)d[a[i].to]=true;
}
}
void Print(int x)
{
printf("%d ",x);
for(int i=head[x];i;i=a[i].next){
if(a[i].to!=S && a[i].dis==INF-)Print(a[i].to-n);
}
}
int main()
{
int x,y;
n=gi();m=gi();
T=*n+;
for(int i=;i<=n;i++)init(S,i,),init(i+n,T,);
for(int i=;i<=m;i++){
x=gi();y=gi();
init(x,y+n,INF);
}
int tp=maxflow();
hfs();
for(int i=;i<=n;i++){
if(!d[i+n])continue;
Print(i);
printf("\n");
}
printf("%d",n-tp);
}