最小路径覆盖详解

定义：通俗点讲，就是在一个有向图中，找出最少的路径，使得这些路径经过了所有的点。

而最小路径覆盖又分为：最小不相交路径覆盖 和 最小可相交路径覆盖。

最小不相交路径覆盖 ： 就是我们找到的每条路径不能相交，就是每条路径不能有同一个点。
最小可相交路径覆盖 ： 这个与上面相对应，就是可以相交。

注意：每个点被自己覆盖，路径长度为0

求解最小不相交路径覆盖： 我们把每个点都拆成两个点，分为入点和出点，如果 u 到 v 有边，那么我们就让 u 的入点连向 v 的出点 ， 最后跑一下最大流或者匈牙利 算出最大匹配。答案就是 点的数目 - 最大匹配数

求解最小可相交路径覆盖： 和上面很相似，但是我们再跑最大匹配时，我们先对原图进行一次闭包传递(通过Warshell传递闭包算法)，然后过程就一样了。

最小不相交路径覆盖题目：POJ - 1422

AC代码：

#pragma GCC optimize(2)
#include<cstring>
#include<iostream>
#define int long long
using namespace std;
const int N=250;
int T,n,m,mat[N],vis[N],res;
int head[N],nex[N*N],to[N*N],tot;
void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot; 
}
bool find(int x,int id){
	for(int i=head[x];i;i=nex[i]){
		if(vis[to[i]]!=id){
			vis[to[i]]=id;
			if(!mat[to[i]]||find(mat[to[i]],id)){
				mat[to[i]]=x;	return 1;
			}
		}
	}
	return 0;
}
signed main(){
	cin>>T;
	while(T--){
		memset(head,0,sizeof head);	res=tot=0;
		memset(mat,0,sizeof mat);	memset(vis,0,sizeof vis);	
		cin>>n>>m;
		while(m--){
			int a,b;	cin>>a>>b;	add(a,b);
		}
		for(int i=1;i<=n;i++)	res+=find(i,i);
		cout<<n-res<<endl;
	}
	return 0;
}

最小可相交路径覆盖题目：POJ - 2594

AC代码：

#pragma GCC optimize(2)
#include<cstring>
#include<iostream>
#define int long long
using namespace std;
const int N=510;
int n,m,mat[N],vis[N],g[N][N],res;
void Warshell(){
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(g[i][k]&&g[k][j])	g[i][j]=1;
}
bool find(int x,int id){
	for(int i=1;i<=n;i++){
		if(g[x][i]&&vis[i]!=id){
			vis[i]=id;
			if(!mat[i]||find(mat[i],id)){
				mat[i]=x;	return 1;
			}
		}
	}
	return 0;
}
signed main(){
	while(cin>>n>>m,n||m){
		memset(g,0,sizeof g);	memset(vis,0,sizeof vis);
		memset(mat,0,sizeof mat);	res=0;
		while(m--){
			int a,b;	cin>>a>>b;	g[a][b]=1;
		}
		Warshell();
		for(int i=1;i<=n;i++)	res+=find(i,i);
		cout<<n-res<<endl;
	}
	return 0;
}