本文共 1599 字，大约阅读时间需要 5 分钟。

题目大意： 给出一个DAG，要找出最少的路径，满足覆盖所有点，并且路径之间不相交。

题解

有一个结论：路径数=点数-被覆盖边数。

证明很简单，因为每一条路径上都会有边数$+1$个点，所以对于每条路径，都满足路径数(1)+边数=点数。

由于要让路径数最小，所以要求出最大的被覆盖边数。

于是把每个点拆开得到一张二分图，对于原图中的一条边 $(x,y)$，在二分图中连一条从左边的 $x$ 到右边的 $y$ 的边。然后源点向左边的点连边，右边的点向汇点连边，跑一发最大流就得到了最大被覆盖边数。

由于每个点只会在一条路径中，所以每个点的后继点都是唯一的，跑网络流的时候顺便记录下来即可求出所有路径。

代码如下：

#include 
   
    #include 
    
     #include 
     
      using namespace std;#define maxn 100010int n,m,S,T;struct edge{
   int y,z,next;};edge e[maxn<<1];int first[maxn],len=1;void buildroad(int x,int y,int z){
   	e[++len]=(edge){
   y,z,first[x]};	first[x]=len;}int h[maxn],q[maxn],st,ed;bool bfs(){
   	memset(h,0,sizeof(h));	st=ed=1;q[st]=S;h[S]=1;	while(st<=ed)	{
   		int x=q[st++];		for(int i=first[x];i;i=e[i].next)		if(!h[e[i].y]&&e[i].z)h[q[++ed]=e[i].y]=h[x]+1;	}	return h[T];}int to[maxn];bool v[maxn];int dfs(int x,int flow){
   	if(x==T)return flow;	int tt=0,p;	for(int i=first[x];i;i=e[i].next)	{
   		int y=e[i].y;		if(h[y]==h[x]+1&&e[i].z)		{
   			p=dfs(y,min(e[i].z,flow-tt));tt+=p;			if(p>0)			{
   				e[i].z-=p;e[i^1].z+=p;to[x]=y;				if(x!=S&&y-n>0)v[y-n]=true;				if(tt==flow)break;				}		}	}	if(!tt)h[x]=0;	return tt;}int main(){
   	scanf("%d %d",&n,&m);S=2*n+1,T=S+1;	for(int i=1;i<=n;i++)	buildroad(S,i,1),buildroad(i,S,0),	buildroad(i+n,T,1),buildroad(T,i+n,0);	for(int i=1,x,y;i<=m;i++)scanf("%d %d",&x,&y),	buildroad(x,y+n,1),buildroad(y+n,x,0);	int ans=0;while(bfs())ans+=dfs(S,999999999);	for(int i=1;i<=n;i++)	if(!v[i])	{
   		int j=i;printf("%d ",j);		while(to[j]!=T&&to[j])j=to[j]-n,printf("%d ",j);		printf("\n");	}	printf("%d",n-ans);}
     
    
   

转载地址：http://zjnib.baihongyu.com/