洛谷 [P1402] 酒店之王

洛谷 [P1402] 酒店之王 有两个约束条件的二分图匹配

我们回忆一下二分图匹配的匈牙利算法的具体流程，它是通过寻找增广路来判断最大匹配数的，我们再观察一下题目中的两个条件，只有两个条件都满足，才算找到一条增广路，所以我们可以分别寻找判断两个条件。

即对两个二分图交替匹配，只有两个二分图都能找到增广路时，才算是一次匹配完成。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

int init(){

	int rv=0,fh=1;

	char c=getchar();

	while(c<'0'||c>'9') {

		if(c=='-') fh=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9'){

		rv=(rv<<1)+(rv<<3)+c-'0';

		c=getchar();

	}

	return fh*rv;

}

int n,p,q,g[2][105][105],match[2][105];

bool f[2][105];

bool dfs(int u,bool no,int rt){

	for(int i=1;i<=g[no][u][0];i++){

		int v=g[no][u][i];

		if(!f[no][v]){

			f[no][v]=1;

			if(no){

				if(!match[no][v]||dfs(match[no][v],no,rt)){

					match[no][v]=u;

					return 1;

				}

			}else{

				if(!match[no][v]){

					if(dfs(rt,1,rt)) {

						match[no][v]=u;

						return 1;

					}

				}else if(dfs(match[no][v],no,rt)){

					match[no][v]=u;

					return 1;

				}

			}

		}

	}

	return 0;

}

int main(){

	n=init();p=init();q=init();

	for(int i=1;i<=n;i++){

		for(int j=1;j<=p;j++){

			int t=init();

			if(t){

				g[0][i][++g[0][i][0]]=j;

			}

		}

	}

	for(int i=1;i<=n;i++){

		for(int j=1;j<=q;j++){

			int t=init();

			if(t){

				g[1][i][++g[1][i][0]]=j;

			}

		}

	}

	int ans=0;

	for(int i=1;i<=n;i++){

		memset(f,0,sizeof(f));

		if(dfs(i,0,i)) ans++;

	}

	cout<<ans<<endl;

	return 0;

}