[洛谷P2764] 最小路径覆盖

问题描述

给定有向图 G=(V,E) 。设 P 是 G 的一个简单路(顶点不相交)的集合。如果 V 中每个定点恰好在P的一条路上，则称 P 是 G 的一个路径覆盖。P中路径可以从 V 的任何一个定点开始，长度也是任意的，特别地，可以为 0 。G 的最小路径覆盖是 G 所含路径条数最少的路径覆盖。设计一个有效算法求一个 DAG (有向无环图) G 的最小路径覆盖。

输入格式

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

输出格式

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

链接

洛谷

解析

由已知条件，每个点的入度和出处均为0。为满足这一限制，不妨将每个点(x)拆成两个点(x1,x2)，源点向其中一个连边，另一个向汇点连边。对于原图上存在的边((u,v))，我们从(u1)向(v2)连边。每条边的容量均为1，代表度数限制。这张图的最大流显然是(n)，那么我们只需要跑一边最大流，然后对于残量网络上原图对应的边，如果满流说明路径覆盖集中包含这条边，输出即可。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define N 152
#define M 6002
using namespace std;
const int inf=1<<30;
int head[2*N],ver[M*2],nxt[M*2],cap[M*2],l;
int head1[N],ver1[M],nxt1[M],l1;
int n,m,i,j,s,t,dis[2*N],d[N],ans;
int read()
{
	char c=getchar();
	int w=0;
	while(c<'0'||c>'9') c=getchar();
	while(c<='9'&&c>='0'){
		w=w*10+c-'0';
		c=getchar();
	}
	return w;
}
void insert(int x,int y,int z)
{
	ver[l]=y;
	cap[l]=z;
	nxt[l]=head[x];
	head[x]=l;
	l++;
	ver[l]=x;
	nxt[l]=head[y];
	head[y]=l;
	l++;
}
bool bfs()
{
	queue<int> q;
	memset(dis,-1,sizeof(dis));
	q.push(s);
	dis[s]=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i!=-1;i=nxt[i]){
			int y=ver[i];
			if(dis[y]==-1&&cap[i]>0){
				dis[y]=dis[x]+1;
				q.push(y);
			}
		}
	}
	return (dis[t]>0);
}
int dfs(int x,int flow)
{
	if(x==t||flow==0) return flow;
	int ans=0;
	for(int i=head[x];i!=-1;i=nxt[i]){
		int y=ver[i];
		if(dis[y]==dis[x]+1&&cap[i]>0){
			int a=dfs(y,min(flow,cap[i]));
			ans+=a;
			flow-=a;
			cap[i]-=a;
			cap[i^1]+=a;
		}
		if(flow==0) break;
	}
	if(flow) dis[x]=-1;
	return ans;
}
void Dinic()
{
	int ans=0;
	while(bfs()) ans+=dfs(s,inf);	
}
void insert1(int x,int y)
{
	l1++;
	ver1[l1]=y;
	nxt1[l1]=head1[x];
	head1[x]=l1;
	d[y]++;
}
void print(int x)
{
	printf("%d ",x);
	for(int i=head1[x];i;i=nxt1[i]) print(ver1[i]);
}
int main()
{
	memset(head,-1,sizeof(head));
	n=read();m=read();
	t=2*n+1;
	for(i=1;i<=n;i++) insert(s,i,1),insert(n+i,t,1);
	for(i=1;i<=m;i++){
		int u=read(),v=read();
		insert(u,n+v,1);
	}
	Dinic();
	for(i=1;i<=n;i++){
		for(j=head[i];j!=-1;j=nxt[j]){
			if(ver[j]!=s&&cap[j]==0) insert1(i,ver[j]-n);
		}
	}
	for(i=1;i<=n;i++){
		if(d[i]==0) ans++,print(i),puts("");
	}
	printf("%d
",ans);
	return 0;
}