题目描述
给定有向图 G=(V,E)G=(V,E) 。设 P 是 G 的一个简单路(顶点不相交)的集合。如果 V 中每个定点恰好在P的一条路上，则称 P 是 G 的一个路径覆盖。P中路径可以从 V 的任何一个定点开始，长度也是任意的，特别地，可以为 0 。G 的最小路径覆盖是 G 所含路径条数最少的路径覆盖。设计一个有效算法求一个 GAP (有向无环图) G 的最小路径覆盖。
输入输出格式 输入格式： 第一行有 2 个正整数 n 和 m 。 nn 是给定GAP(有向无环图) G的顶点数， m 是 G 的边数。接下来的 m 行,每行有两个正整数 i 和 j 表示一条有向边 (i,j)(i,j)。 输出格式： 从第1 行开始，每行输出一条路径。文件的最后一行是最少路径数。思路
算法：把原图的每个点V拆成\(Vx\)和\(Vy\)两个点，如果有一条有向边A->B，那么就加边
\(Ax\)−>\(By\)\(Ax\)−>\(By\)。 这样就得到了一个二分图。那么最小路径覆盖=原图的结点数-新图的最大匹配数。代码
#include#define inf 1<<30using namespace std;const int maxn=300+50,maxm=12000+10;int head[maxn],succ[maxn];bool vis[maxn];int n,m;int s,t;int size=1;struct edge{ int to,next,cap;}e[maxm];inline int read(){ int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f;}void addedge(int u,int v,int val){ e[++size].to=v;e[size].cap=val;e[size].next=head[u];head[u]=size; e[++size].to=u;e[size].cap=0;e[size].next=head[v];head[v]=size;}int dfs(int u,int f){ if(u==t) return f; vis[u]=1; for(int i=head[u];i;i=e[i].next) { int to=e[i].to; if(!vis[to]&&e[i].cap>0) { int d=dfs(to,min(f,e[i].cap)); if(d>0) { succ[u]=to; e[i].cap-=d; e[i^1].cap+=d; return d; } } } return 0;}int maxflow(){ int flow=0; while(1) { memset(vis,0,sizeof(vis)); int f=dfs(s,inf); if(f==0)return flow; flow+=f; }}int main(){ n=read(),m=read(); s=0,t=2*n+1; for(int i=1;i<=n;i++) addedge(s,i,1),addedge(i+n,t,1); for(int i=1;i<=m;i++) { int u=read(),v=read(); addedge(u,v+n,1); } int flow=maxflow(); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { int u=i; if(!vis[u]) { vis[u]=1; printf("%d ",u); while(succ[u]&&succ[u]!=t) { u=succ[u]; u-=n; vis[u]=1; printf("%d ",u); } printf("\n"); } } printf("%d\n",n-flow); return 0;}