P2055 [ZJOI2009]假期的宿舍 题解 暨 二分图最大匹配(匈牙利算法) 模板

匈牙利算法可以在\(O(n^3)\)的时间复杂度内求出二分图最大匹配.方法是:依次考虑每个左边点,对于每个人考虑每个右边点,找到第一个有边的右边点,如果没有匹配,就匹配,如果已经匹配,使用NTR技术让其匹配重新匹配.

二分图板子题,但莫名其妙很难写对.个人很反感这种用题意绕弯子来考人的题.

#include
#include
#include
using namespace std;
const int N=105;
int T,n,a,cnt,tot,sum;
int school[N],home[N],vis[N],p[N];
int head[N];
struct edge{
	int to,next;
} e[N*N];
void add(int u,int v){
	e[++cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
bool match(int k) {
	for (int i=head[k];i;i=e[i].next) {
		int v=e[i].to;
		if (vis[v]) continue;
		vis[v]=1;
		if (!p[v]||match(p[v])) {
			p[v]=k;
			return true;
		}
	}
	return false;
}
int main() {
	ios::sync_with_stdio(false);
	cin>>T;
	while (T--) {
		cnt=0,tot=0,sum=0;
		memset(head,0,sizeof(head));
		memset(p,0,sizeof(p));
		cin>>n;
		for (int i=1; i<=n; i++)
			cin>>school[i];
		for (int i=1; i<=n; i++) {
			cin>>home[i];
			if (home[i]==0&&school[i])
			add(i,i);
		}
		for (int i=1; i<=n; i++)
			if (!school[i]||(school[i]&&!home[i]))
				++tot;
		for (int i=1; i<=n; i++)
			for (int j=1; j<=n; j++) {
				cin>>a;
				if (a&&school[j])
					add(i,j);
			}
		for (int i=1; i<=n; i++) {
			if ((school[i]&&home[i]==0)||!school[i]) {
				memset(vis,0,sizeof(vis));
				if (match(i)) ++sum;
			}
		}
		if (sum==tot)
			cout<<"^_^"<