最小路径覆盖问题

题目

求有向无环图的最小路径覆盖（可以从任意一个点开始）

题目链接：洛谷P 2764

二分图性质：最小路径覆盖 == 顶点数 - 最大匹配数

所以此题我们可以转化为求最大匹配来做，但是麻烦的是输出路径。

考虑建图：

我们可以把点拆成两个点，分别为入点和出点，让超级源点S连向每个点的入点，让每个点的出点连向超级汇点T，然后如果u能到达v，那么就让u的入点连向v的出点即可。（建图完成）

然后跑一遍最大流，答案就是总的点数 n - dinic()

考虑输出路径：

我们输出路径，主要就是要找到每个边集合开始的边，很多人都用并查集来维护边的关系，但是我觉得完全没有必要，我们考虑一下开始的边的关系，我们可以发现如果当前的点的出点所连接的点，如果没有流量流过来，那么这个点就是开始的点。所以我们可以判断每个点的出点，如果所有点到它的流量都是1，然后我们dfs一遍输出即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=310,M=120010;
int n,m,h[N],s,t,vis[N],f[N];
int head[N],to[M],w[M],nex[M],tot=1;
inline void ade(int a,int b,int c){
	to[++tot]=b; w[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c){
	ade(a,b,c);	ade(b,a,0);
}
int find(int x){
	return x==f[x]?x:f[x]=find(f[x]);
}
int bfs(){
	memset(h,0,sizeof h);	queue<int> q;	q.push(s);	h[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(w[i]&&!h[to[i]]){
				h[to[i]]=h[u]+1;	q.push(to[i]);
			}
		}
	}
	return h[t];
}
int dfs(int x,int f){
	if(x==t)	return f;
	int fl=0;
	for(int i=head[x];i&&f;i=nex[i]){
		if(w[i]&&h[to[i]]==h[x]+1){
			int mi=dfs(to[i],min(w[i],f));
			w[i]-=mi;	w[i^1]+=mi;	fl+=mi;	f-=mi;
		}
	}
	if(!fl)	h[x]=-1;
	return fl;
}
int dinic(){
	int res=0;
	while(bfs())	res+=dfs(s,0x3f3f3f3f);
	return res;
}
void out(int x){
	printf("%d ",x);
	for(int i=head[x*2-1];i;i=nex[i]){
		if(!w[i]&&to[i]!=s)	out(to[i]/2);
	}
}
signed main(){
	cin>>n>>m;	s=0,t=2*n+2;
	for(int i=1;i<=n;i++){
		add(s,i*2-1,1);	add(i*2,t,1);
	}
	for(int i=1;i<=m;i++){
		int a,b;	cin>>a>>b;	add(a*2-1,b*2,1);
	}
	int res=n-dinic();
	for(int i=1;i<=n;i++){
		int flag=0;
		for(int j=head[i*2];j&&!flag;j=nex[j]){
			if(to[j]!=t&&!w[j^1])	flag++;
		}
		if(!flag)	out(i),puts("");
	}
	cout<<res<<endl;
	return 0;
}