二分图水题

题目描述

学校放假了……有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。

比如 A 和 B 都是学校的学生，A 要回家，而 C 来看B，C 与 A 不认识。我们假设每个人只能睡和自己直接认识的人的床。那么一个解决方案就是 B 睡 A 的床而 C 睡 B 的床。而实际情况可能非常复杂，有的人可能认识好多在校学生，在校学生之间也不一定都互相认识。

我们已知一共有 n 个人，并且知道其中每个人是不是本校学生，也知道每个本校学生是否回家。问是否存在一个方案使得所有不回家的本校学生和来看他们的其他人都有地方住。

原题链接

Solve

首先，我们得知道二分图最大匹配和匈牙利算法。
然后，就很简单了。
建图，每个不回家在校学生可睡自己的床也可白嫖其他认识的在校学生的床，非在校学生可白嫖认识的在校学生的床。
匈牙利算法。
注意重置

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1010
using namespace std;
int t;
int n;
int head[N*N],to[N*N],nxt[N*N],len;
int sis[N],mis[N],num,hb[N];
bool vis[N];
void add(int u,int v){
	to[++len]=v;
	nxt[len]=head[u];
	head[u]=len;
}
bool zm(int u){
	for(int i=head[u];i!=-1;i=nxt[i]){
		int v=to[i];
		if(vis[v]) continue;
		vis[v]=true;
		if(!hb[v]||zm(hb[v])){
			hb[v]=u;
			return true;
		}
	}
	return false;
}
bool check(int u){
	memset(vis,false,sizeof(vis));
	return zm(u);
}
int main()
{
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		len=0;
		bool flag=false;
		memset(head,-1,sizeof(head));
		memset(hb,0,sizeof(hb));		
		for(int i=1;i<=n;i++) scanf("%d",&sis[i]);
		for(int i=1;i<=n;i++){
			scanf("%d",&mis[i]);
			if(sis[i]&&!mis[i]) add(i,i+n);
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				scanf("%d",&num);
				if(sis[i]==1&&mis[i]==1) continue;
				if(num==1&&sis[j]==1) add(i,j+n);
			}
		}
		for(int i=1;i<=n;i++){
			if(sis[i]==1&&mis[i]==1) continue;
			if(!check(i)){
				flag=true;
				printf("T_T\n");
				break;
			} 
		}
		if(!flag) printf("^_^\n");
	}
	return 0;
}

后言T_T

蒟蒻本想写“浅谈二分图最大匹配”来着，但是水平不够，就搁浅了。T_T