最小不相交路径覆盖

本文主要是介绍最小不相交路径覆盖，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

例1

hdoj 1151 air raid

有一张有向图，一些伞兵可以落在任意位置，沿着有向边往前走。注意一条路仅能被一个伞兵经过

问最少派出多少个伞兵

题解

这是一个最小（不相交）路径覆盖问题，因为从每个点出发，下一步最多经过一条边，因此可以用二分匹配解决（可以想见）

code

#include<bits/stdc++.h>   //二分匹配 
#define ll long long
using namespace std;
int n,m,p;
bool g[505][505],reserved[505];
int ans[505];

bool dfs(int now){
	for(int i=1;i<=n;i++){
		if(!reserved[i]&&g[now][i]){
			reserved[i]=1;
			if(ans[i]==-1||dfs(ans[i])){
				ans[i]=now;
				return 1;
			}
		}
	}
	return 0;
}

int main(){
	int t;cin>>t;
	while(t--){
		cin>>n>>m;
		
		memset(g,0,sizeof(g));
		memset(ans,-1,sizeof(ans));
		
		for(int i=1,x,y,z;i<=m;i++){
			scanf("%d%d",&x,&y);
			g[x][y]=1;
		}
		
		int anss=0;
		for(int i=1;i<=n;i++){
			memset(reserved,0,sizeof(reserved));
			if(dfs(i)) anss++;
		}
		
		cout<<n-anss<<endl;
	}
	return 0;
}

例2

hdoj 3861

缩点后，转化成最小路径覆盖问题

code

#include<bits/stdc++.h>   
#define ll long long      
using namespace std;
struct Edge{
	int to,nex;
}e[2][100005];
int head[2][10004],q[11005],f[11005],a[10005],va[10005],dp[10005];
int n,m,cnt[2],t;
bool vis[10005];
int x[100005],y[100005];
vector<int>v[10005];
int anss; 
int match[5005];  //下标是配对的b方  值为对应的a方 
bool reserve_b[5005];

void init(){
	memset(head,0,sizeof(head));
	memset(vis,0,sizeof(vis));
	memset(match,0,sizeof(match));
	for(int i=1;i<=n;i++)v[i].clear();  //
	t=0;
	cnt[0]=cnt[1]=0;
}

void add(int u,int v){
	cnt[0]++;
	e[0][cnt[0]].to=v;
	e[0][cnt[0]].nex=head[0][u];
	head[0][u]=cnt[0];
}

void add2(int u,int v){
	cnt[1]++;
	e[1][cnt[1]].to=v;
	e[1][cnt[1]].nex=head[1][u];
	head[1][u]=cnt[1];
}

void dfs1(int now){
	vis[now]=1;
	for(int i=head[0][now];i;i=e[0][i].nex){
		int x=e[0][i].to;
		if(!vis[x]) dfs1(x);
	}
	q[++t]=now;
}

void dfs2(int now,int y){
	vis[now]=0;  f[now]=y;
	for(int i=head[1][now];i;i=e[1][i].nex){
		int x=e[1][i].to;
		if(vis[x]) dfs2(x,y);
	}
}

//二分图匹配  
bool dfs(int now){
	for(int i=0;i<v[now].size();i++){
		int x=v[now][i];
		if(!reserve_b[x]){
			reserve_b[x]=1;
			if(!match[x]||dfs(match[x])){  //b无配对 或者 b的原配可以找到新的配对 
				match[x]=now;  //则令x为b的配对 
				return 1;  //x找到了配对 
			}
		}
	}
	return 0;
}

int main(){
	int T;cin>>T; 
	while(T--){
		cin>>n>>m;
		init();
		for(int i=1;i<=m;i++){
			scanf("%d%d",&x[i],&y[i]);
			add(x[i],y[i]);
			add2(y[i],x[i]);
		}
		for(int i=1;i<=n;i++){
			if(!vis[i]){
				dfs1(i);
			}
		}
		for(int i=n;i>=1;i--){
			if(vis[q[i]]){
				dfs2(q[i],q[i]);
			}
		}
		
		
		for(int i=1;i<=m;i++){
			if(f[x[i]]!=f[y[i]]) v[f[x[i]]].push_back(f[y[i]]);
		}
		set<int>st;
		for(int i=1;i<=n;i++){
			st.insert(f[i]);
			va[f[i]]+=a[i];
		}
		
		anss=0;
		for(auto i=st.begin();i!=st.end();i++){  //a方 
			memset(reserve_b,0,sizeof(reserve_b));  //不加会错
			if(dfs(*i)) anss++;  //ai配对成功后配对数++，虽然可能更换配对，但是保证ai一定有配对 
		}
		cout<<st.size()-anss<<endl;
	} 
	
	return 0;
}

这篇关于最小不相交路径覆盖的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！