洛谷 P2055 [ ZJOI 2009 ] 假期的宿舍 —— 二分图匹配

时间:2024-08-22 23:07:38

题目:https://www.luogu.org/problemnew/show/P2055

二分图匹配;

注意要连边的话对方必须有床!

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int T,n,hd[],ct,pre[];
bool in[],hm[],vis[];
struct N{
int to,nxt;
N(int t=,int n=):to(t),nxt(n) {}
}ed[];
void add(int x,int y){ed[++ct]=N(y,hd[x]); hd[x]=ct;}
bool dfs(int x)
{
for(int i=hd[x],u;i;i=ed[i].nxt)
{
if(vis[u=ed[i].to])continue;
vis[u]=;
if(!pre[u]||dfs(pre[u])){pre[u]=x; return ;}
}
return ;
}
int main()
{
scanf("%d",&T);
while(T--)
{
ct=;
memset(hd,,sizeof hd);
memset(in,,sizeof in);
memset(hm,,sizeof hm);
memset(pre,,sizeof pre);
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&in[i]);
if(in[i])add(i,i);
}
for(int i=;i<=n;i++)
{
scanf("%d",&hm[i]);
}
for(int i=,x;i<=n;i++)
for(int j=;j<=n;j++)
{
scanf("%d",&x);
if(x&&in[j])add(i,j);//对方要有床!!!
}
bool fl=;
for(int i=;i<=n;i++)
{
if(in[i]&&hm[i])continue;
memset(vis,,sizeof vis);
if(!dfs(i)){fl=; break;}//!
}
if(!fl)printf("%c%c%c\n",,,);
else printf("%c%c%c\n",,,);
}
return ;
}