算法实现题8-3 最小路径覆盖问题（习题 8-13）
´问题描述： 给定有向图 G=(V,E)。设 P 是 G 的一个简单路（顶点不相交）的集合。如果 V 中每个顶点恰好在 P 的一条路上，则称 P是 G 的一个路径覆盖。P 中路径可以从 V 的任何一个顶点开始，长度也是任意的，特别地，可以为0。G 的最小路径覆盖是G 的所含路径条数最少的路径覆盖。 设计一个有效算法求一个有向无环图G 的最小路径覆盖。 编程任务： 对于给定的给定有向无环图G，编程找出 G的一个最小路径覆盖。 ´数据输入： 由文件input.txt提供输入数据。文件第1 行有 2个正整数 n和 m。n是给定有向无环图G 的顶点数， m是G 的边数。 接下来的 m行， 每行有 2 个正整数 i和 j， 表示一条有向边(i,j)。 ´结果输出: 程序运行结束时，将最小路径覆盖输出到文件 output.txt 中。从第 1 行开始，每行输出一条路径。文件的最后一行是最少路径数。输入文件示例
input.txt 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输出文件示例
output.txt 1 4 7 10 11 2 5 8 3 6 9 3_______________________________
把每个点i拆成 xi和yi,如果有边｛i, j}，则 建一条权值为1的｛yi,xj}的边.
最后建边 ｛s,xi}和{yi,t}权值都为1。
因为当每个点各自为一条简单路时，最小路径覆盖即为n，所以有两个点连条边，那么最小路径覆盖可以减1，所以最后n-flow 即为答案
_______________________________
1 Program Stone; 2 var i,n,m,le,s,t,flow:longint; 3 head,dis,vh,cur,last,pre:array[0..20000]of longint; 4 next,date,point:array[-20000..20000]of longint; 5 procedure add(x,y:longint); 6 begin 7 inc(le); 8 date[le]:=1; 9 point[le]:=y;10 next[le]:=head[x];11 head[x]:=le;12 point[-le]:=x;13 next[-le]:=head[y];14 head[y]:=-le;15 end;16 procedure init;17 var i,j,k:longint;18 begin19 readln(n,m);20 s:=0;t:=2*n+1;21 for i:=1 to m do22 begin23 readln(j,k);24 add(j,k+n);25 end;26 for i:=1 to n do27 begin28 add(s,i);29 add(i+n,t);30 end;31 end;32 procedure print;33 var i,j:longint;34 begin35 for i:=n+1 to n+n do36 if pre[i]=0 then37 begin38 j:=i-n;39 while j>0 do40 begin41 write(j,' ');42 j:=last[j]-n;43 end;44 writeln;45 end;46 writeln(n-flow);47 end;48 function min(a,b:longint):longint;49 begin50 if a0 do59 begin60 if (date[i]>0)and(dis[x]=dis[point[i]]+1) then61 begin62 cur[x]:=i;63 d:=aug(point[i],min(l,date[i]));64 if (d>0)and(x<=n)and(x>s) then begin last[x]:=point[i];pre[point[i]]:=1;end;65 dec(date[i],d);66 inc(date[-i],d);67 dec(l,d);68 if (dis[s]=t+1)or(l=0) then exit(nf-l);69 end;70 i:=next[i];71 end;72 if l=nf then73 begin74 minh:=t;75 i:=head[x];76 while i<>0 do77 begin78 if (date[i]>0)and(dis[point[i]]