题目：
给定有向图G=(V,E)。设P是G的一个简单路（顶点不相交）的集合。如果V中每个顶点恰好在P的一条路上，则称P是G的一个路径覆盖。P中路径可以从V的任何一个顶点开始，长度也是任意的，特别地，可以为0。G的最小路径覆盖是G的所含路径条数最少的路径覆盖。
设计一个有效算法求一个有向无环图G的最小路径覆盖。
输入格式：
第1行有2个正整数n和m。n是给定有向无环图G的顶点数，m是G的边数。
接下来的m行，每行有2个正整数i 和j，表示一条有向边(i,j)。
输出格式：
从第一行开始，每行输出1条路径，文件的最后一行是最小路径数。
链接： https://loj.ac/problem/6002
思路：
我们将每个点拆成i和i+n，因为顶点不相交，那么这个图就成了一个二分图
最小路径覆盖=顶点数-二分图最大匹配
证明:我们先把每个顶点看成一条单独的路径，花费记为1，假设一开始有11个点，那么总花费是11，此时如果有一条边连接了1和2，即1和2匹配，那么总花费变成10
所以要想用最小的路径覆盖所有顶点，那么要求出这个二分图中的最大匹配，用顶点总数减去二分图最大匹配即为答案。跑一遍最大流来求二分图的最大匹配。
然后输出路径的方法是：如果这条边上的流量为0，那么说明经过了这条路径，再以这个点为起点继续寻找，跑一遍dfs即可
代码：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> using namespace std; const int MAXN=2e5+5; const int INF=0x7fffffff; typedef long long ll; int head[MAXN],tot,visit[MAXN]; int s,t,n,m; struct node { int to,nxt,flow; }e[MAXN]; void add(int x,int y,int z) { e[tot].to=y;e[tot].nxt=head[x];e[tot].flow=z;head[x]=tot++; } void add_edge(int x,int y,int z) { add(x,y,z);add(y,x,0); } int deep[MAXN],l,r,q[MAXN]; bool bfs() { memset(deep,0,sizeof(deep)); l=0,r=0; deep[s]=1;q[++r]=s; while(l!=r) { int u=q[++l]; for(int i=head[u];~i;i=e[i].nxt) { int v=e[i].to; if(!deep[v]&&e[i].flow) { deep[v]=deep[u]+1; q[++r]=v; } } } return deep[t]; } int dfs(int u,int min_f) { if(u==t)return min_f; int temp_f=0; for(int i=head[u];~i&&min_f;i=e[i].nxt) { int v=e[i].to; if(deep[v]==deep[u]+1&&e[i].flow) { int d=dfs(v,min(min_f,e[i].flow)); if(d>0) { min_f-=d; temp_f+=d; e[i].flow-=d; e[i^1].flow+=d; } } } if(!temp_f)deep[u]=-1; return temp_f; } int dinic() { int res=0; while(bfs()) res+=dfs(s,INF); return res; } vector<int>path; void print(int u) { if(visit[u])return; visit[u]=1; path.push_back(u); for(int i=head[u];~i;i=e[i].nxt) { int v=e[i].to; if(e[i].flow==0&&v>n&&v<=2*n&&!visit[v]) print(v-n); } } int main() { scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); s=0,t=2*n+2; for(int i=1;i<=n;i++) add_edge(s,i,1); for(int i=n+1;i<=2*n;i++) add_edge(i,t,1); for(int i=1;i<=m;i++) //注意这里连边的时候要将x与y拆分出来的那个点相连 { int x,y;scanf("%d%d",&x,&y); add_edge(x,y+n,1); } int ans=dinic(); for(int i=1;i<=n;i++) { print(i); if(path.size()) //输出路径 { for(int i=0;i<path.size();i++) printf("%d%c",path[i],i==path.size()-1?‘\n‘:‘ ‘); path.clear(); } } printf("%d\n",n-ans); return 0; }
原文：https://www.cnblogs.com/ljxdtc666/p/12377108.html