最小路径覆盖问题

题意简述

给出一个有向图$G=(V,E)$，求出简单路径（你可以理解为一条链）数量最少的覆盖集，使得覆盖集中所有简单路径之间无相交节点，且集合中所有节点集合等于$V$。简单路径可以只包含一个节点。

题解

考虑每一个节点处在简单路径中存在两个状态：前驱和后继。由这两个状态可唯一地确定一条经过该节点的简单路径。且只要满足前驱和后继都是唯一的，那么所有的简单路径之间都不会相交。

所以考虑将一个节点$u$拆分成$u$和$u'$，对于边$(u, v)$，由$u$向$v'$连边。这样一来，若$u$选择了$v'$，则说明$u$的后继是$v$；若$u'$被$v$选择，说明$u$的前驱是$v$。如此一来，该题就转化成了二分图匹配问题。

假设一开始我所拥有的覆盖集为所有的单独节点构成的简单路径，若我能成功地增加一个匹配，那么简单路径的数量就会减一。所以，只要求出了最大二分图匹配数，假设为$x$，点数为$n$，那么最小覆盖集的元素个数即为$n-x$。

方案的求解大致就是这样：

1. 找到一个没有前驱的节点；
2. 向后继走，走到没有后继为止。

代码

#include <cstdio>
#include <cstring>
const int maxn=300+10;
const int maxm=10000+10;
const int INF=0x3f3f3f3f;
int cur[maxn],head[maxn],to[maxm<<1],nxt[maxm<<1],val[maxm<<1];
int tot=1;
int n,m;
int s,t;
int dep[maxn];
int l[maxn],r[maxn];
struct Queue
{
	int a[maxn];
	int l,r;
	Queue() {l=1,r=0;}
	void push(int x) {a[++r]=x;}
	void pop() {l++;}
	int front() {return a[l];}
	bool empty() {return l>r;}
}q;

int min(int x,int y) {return x<y?x:y;}
void add(int u,int v,int w)
{
	nxt[++tot]=head[u];
	head[u]=tot;
	to[tot]=v;
	val[tot]=w;
}
bool bfs()
{
	memset(dep, 0x3f, sizeof(dep));
	dep[s]=0;
	q=Queue();
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for (int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			if (val[i]>0&&dep[v]>dep[u]+1)
			{
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	return dep[t]!=INF;
}
int dfs(int u,int minf)
{
	if (u==t)
		return minf;

	int used=0;
	for (int &i=cur[u];i;i=nxt[i])
	{
		int v=to[i];
		if (val[i]>0&&dep[v]==dep[u]+1)
		{
			int flow=dfs(v, min(minf-used, val[i]));
			if (flow)
			{
				used+=flow;
				val[i]-=flow;
				val[i^1]+=flow;
				if (used==minf)
					break;
			}
		}
	}
	return used;
}
int main()
{	
	scanf("%d%d",&n,&m);

	for (int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u, n+v, 1),add(n+v, u, 0);
	}
	s=0,t=2*n+1;
	for (int i=1;i<=n;i++)
	{
		add(s, i, 1),add(i, s, 0);
		add(n+i, t, 1),add(t, n+i, 0);
	}

	int ans=0;
	while(bfs())
	{
		for (int i=s;i<=t;i++)
			cur[i]=head[i];
		ans+=dfs(s, INF);
	}

	for (int u=1;u<=n;u++)
		for (int i=head[u];i;i=nxt[i])
		{
			if (val[i])
				continue;
			int v=to[i];
			if (v!=s)
			{
				r[u]=v-n;
				l[v-n]=u;
				break;
			}
		}

	for (int i=1;i<=n;i++)
		if (!l[i])
		{
			int u=r[i];
			printf("%d",i);
			while(u)
			{
				printf(" %d",u);
				u=r[u];
			}
			putchar('\n');
		}

	printf("%d\n",n-ans);
	return 0;
}