给定有向图G=(V,E)。设P 是G 的一个简单路（顶点不相交）的集合。如果V 中每个顶点恰好在P 的一条路上，则称P是G 的一个路径覆盖。P 中路径可以从V 的任何一个顶点开始，长度也是任意的，特别地，可以为0。G 的最小路径覆盖是G 的所含路径条数最少的路径覆盖。设计一个有效算法求一个有向无环图G 的最小路径覆盖。提示：设V={1，2，.... ，n}，构造网络G1=(V1,E1)如下：

每条边的容量均为1。求网络G1的（ 0 x , 0 y ）最大流。

«编程任务：

对于给定的给定有向无环图G，编程找出G的一个最小路径覆盖。

输入输出格式

输入格式：

 

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

 

输出格式：

 

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

 

输入输出样例

输入样例#1： 

11 121 21 31 42 53 64 75 86 97 108 119 1110 11

输出样例#1： 

1 4 7 10 112 5 83 6 93

说明

1<=n<=150,1<=m<=6000

由@FlierKing提供SPJ

 

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 using namespace std; 9 #define INF 0x3f3f3f3f 10 const int maxn = 6e4+10; 11 int n,m,s,t,u,v; 12 struct Edge { 13 int from, to, cap, flow; 14 }; 15 vector
             
               edges; 16 vector
              
                G[maxn]; 17 bool vis[maxn]; 18 int d[maxn], cur[maxn],nxt[maxn]; 19 20 void Init() 21 { 22 memset(d,0,sizeof d); 23 for(int i=0;i<=2*n+1;i++) G[i].clear(); 24 } 25 26 void AddEdge(int from, int to, int cap) 27 { 28 edges.push_back((Edge){ from, to, cap, 0}); 29 edges.push_back((Edge){to, from, 0, 0}); 30 int m = edges.size(); 31 G[from].push_back(m-2); G[to].push_back(m-1); 32 } 33 34 bool bfs() 35 { 36 memset(vis,0,sizeof vis); 37 queue
               
                 q; 38 q.push(s); 39 d[s] = 0; vis[s] = 1; 40 while (!q.empty()) 41 { 42 int x = q.front(); q.pop(); 43 for(int i = 0; i < G[x].size(); ++i) 44 { 45 Edge &e = edges[G[x][i]]; 46 if (!vis[e.to] && e.cap > e.flow) 47 { 48 vis[e.to] = 1; 49 d[e.to] = d[x] + 1; 50 q.push(e.to); 51 } 52 } 53 } 54 return vis[t]; 55 } 56 57 int dfs(int x,int a) 58 { 59 if(x == t || a == 0) return a; 60 int flow = 0, f; 61 for(int &i = cur[x]; i < G[x].size(); ++i) 62 { 63 Edge &e = edges[G[x][i]]; 64 if (d[e.to] == d[x] + 1 && (f=dfs(e.to, min(a, e.cap-e.flow))) > 0) 65 { 66 e.flow += f; 67 edges[G[x][i]^1].flow -= f; 68 flow += f; a -= f; 69 if (a == 0) break; 70 } 71 } 72 return flow; 73 } 74 75 int MaxFlow(int s, int t) 76 { 77 int flow = 0; 78 while (bfs()) 79 { 80 memset(cur,0,sizeof cur); 81 flow += dfs(s, INF); 82 } 83 return flow; 84 } 85 86 int main() 87 { 88 while(scanf("%d%d",&n,&m)!=EOF) 89 { 90 Init(); 91 for(int i=1;i<=m;i++) 92 { 93 scanf("%d%d",&u,&v); 94 AddEdge(u,v+n,1); 95 } 96 s=0,t=2*n+1; 97 for(int i=1;i<=n;i++) 98 { 99 AddEdge(s,i,1);100 AddEdge(i+n,t,1);101 }102 int ans=MaxFlow(s,t);103 memset(nxt,0,sizeof nxt);104 memset(vis,0,sizeof vis);105 106 for(int i=1;i<=n;i++)107 {108 for(int j=0;j
                
                 0) nxt[e.from]=e.to-n;112 }113 }114 for(int i=1;i<=n;i++)115 {116 if(!vis[i])117 {118 int a=i;119 vis[a]=1;120 printf("%d",a);121 while(nxt[a])122 {123 a=nxt[a];124 vis[a]=1;125 printf(" %d",a);126 }127 printf("\n");128 }129 }130 printf("%d\n",n-ans);131 }132 return 0; 133 }