题目描述
«问题描述：
给定有向图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 行开始，每行输出一条路径。文件的最后一行是最少路径数。
解题思路：
转换一下思路，需要覆盖，那么最多就需要点数条路径。
然后发现，有些路径可以合并，而且每合并一个点集，就少一条路径。
那么什么样的点可以合并呢，就是一条边相连的。
那么将一个点分裂成两个一个用于接受合并，一个用来提供合并。
相连的点，从起点的提供指向终点的接受，流量为$inf$
每个点都可以是起点终点所以向源汇点连$1$的边。
最大流最后拿n减掉就好了。
代码：
1 #include2 #include 3 #include 4 const int oo=0x3f3f3f3f; 5 namespace stb{ 6 template 7 class queue{ 8 public: 9 queue(){h=1,t=0;} 10 int nxt(int x){ if(x+1==1000000)return 1;return x+1;} 11 void push(tnt x){t=nxt(t);l[t]=x;return ;} 12 bool empty(void){ return nxt(t)==h;} 13 tnt front(void){ return l[h];} 14 void clear(void){h=1,t=0;} 15 void pop(void){h=nxt(h);} 16 private: 17 tnt l[1000000]; 18 int h,t; 19 }; 20 }; 21 struct pnt{ 22 int hd; 23 int now; 24 int lyr; 25 int nxt; 26 bool nos; 27 }p[1000]; 28 struct ent{ 29 int twd; 30 int lst; 31 int vls; 32 }e[100000]; 33 int cnt; 34 int n,m; 35 int s,t; 36 stb::queue Q; 37 void ade(int f,int t,int v) 38 { 39 cnt++; 40 e[cnt].twd=t; 41 e[cnt].vls=v; 42 e[cnt].lst=p[f].hd; 43 p[f].hd=cnt; 44 return ; 45 } 46 bool Bfs(void) 47 { 48 Q.clear(); 49 for(int i=1;i<=n*2+2;i++) 50 p[i].lyr=0; 51 p[s].lyr=1; 52 Q.push(s); 53 while(!Q.empty()) 54 { 55 int x=Q.front(); 56 Q.pop(); 57 for(int i=p[x].hd;i;i=e[i].lst) 58 { 59 int to=e[i].twd; 60 if(p[to].lyr==0&&e[i].vls>0) 61 { 62 p[to].lyr=p[x].lyr+1; 63 if(to==t) 64 return true; 65 Q.push(to); 66 } 67 } 68 } 69 return false; 70 } 71 int Dfs(int x,int fll) 72 { 73 if(x==t) 74 return fll; 75 for(int &i=p[x].now;i;i=e[i].lst) 76 { 77 int to=e[i].twd; 78 if(p[to].lyr==p[x].lyr+1&&e[i].vls>0) 79 { 80 int ans=Dfs(to,std::min(fll,e[i].vls)); 81 if(ans>0) 82 { 83 e[i].vls-=ans; 84 e[((i-1)^1)+1].vls+=ans; 85 p[x].nxt=to; 86 if(x!=s) 87 p[to-n].nos=true; 88 return ans; 89 } 90 } 91 } 92 return 0; 93 } 94 void Dinic(void) 95 { 96 int ans=0; 97 while(Bfs()) 98 { 99 for(int i=1;i<=2*n+2;i++)100 p[i].now=p[i].hd;101 int dlt;102 while(dlt=Dfs(s,oo))103 ans+=dlt;104 }105 for(int i=1;i<=n;i++)106 {107 if(!p[i].nos)108 {109 for(int j=i;j!=t-n&&j>0;j=p[j].nxt-n)110 printf("%d ",j);111 puts("");112 }113 }114 printf("%d\n",n-ans);115 return ;116 }117 int main()118 {119 scanf("%d%d",&n,&m);120 s=n*2+1,t=n*2+2;121 for(int i=1;i<=n;i++)122 {123 ade(s,i,1);124 ade(i,s,0);125 ade(i+n,t,1);126 ade(t,n+i,0);127 }128 for(int i=1;i<=m;i++)129 {130 int a,b;131 scanf("%d%d",&a,&b);132 ade(a,b+n,oo);133 ade(b+n,a,0);134 }135 Dinic();136 return 0;137 }