http://codevs.cn/problem/2347/
Solution
二分图板子
连边:i认识j并且j是在校有床 i→j+n
i有床i→i+n
还有就是找要在学校的人,1.有床不回2.没床的(一定来探望)
记录一下二分图最大匹配是否等于要在校的学生即可
福利数据
IN
2
12
0 1 1 0 1 1 1 0 1 0 0 1
1 1 0 1 1 1 1 1 0 1 1 1
0 0 0 1 1 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 1 0 0 1 0 0
1 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0
0 0 1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 1 0 0 0 0 0 0
0 1 0 0 0 1 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0 0 0 1 0
12
0 1 1 1 1 1 1 0 1 1 1 1
1 1 0 1 1 1 1 0 1 1 1 1
0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
1 1 0 0 1 0 0 1 0 0 0 0
0 1 0 1 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 1
0 0 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0
12
1 1 1 0 1 1 0 1 1 0 1 1
0 1 1 1 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 1
0 0 0 0 1 0 1 0 1 1 0 0
0 0 0 1 0 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 1 0 0 0
OUT
T_T
T_T
^_^
Code
// This file is made by YJinpeng，created by XuYike's black technology automatically.
// Copyright (C) 2016 ChangJun High School, Inc.
// I don't know what this program is.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define MOD 1000000007
#define INF 1e9
using namespace std;
typedef long long LL;
const int MAXN=100010;
const int MAXM=100010;
inline int gi() {
register int w=0,q=0;register char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')q=1,ch=getchar();
while(ch>='0'&&ch<='9')w=w*10+ch-'0',ch=getchar();
return q?-w:w;
}
struct Hungarian_dfs{
static const int N=110;
int cnt,n;
int match[N],a[N],c[N];
vector<int>b[N];int f[N];
inline void add(int u,int v){b[u].push_back(v);}
bool dfs(int x){
if(f[x]==cnt)return 0;
int num=b[x].size();f[x]=cnt;
for(int i=0;i<num;i++){
int nex=b[x][i];
if(match[nex]==-1||dfs(match[nex])){
match[x]=nex;match[nex]=x;return 1;
}
}
return 0;
}
void Work(){
int T=gi();
while(T--){
n=gi();int now=0;
for(int i=1;i<=n;i++)a[i]=gi(),b[i].clear();
for(int i=1;i<=n;i++){
c[i]=gi()?a[i]:0;
if(!c[i])now++;
if(a[i])add(i,i+n);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(gi()&&a[j])add(i,j+n);//gi()放前面 逻辑短路
memset(f,false,sizeof(f));int ans=0;
for(int i=1;i<N;i++)match[i]=-1;
for(int i=1;i<=n;i++)
if(match[i]==-1&&!c[i]){
++cnt;if(dfs(i))++ans;else break;
}
printf(ans==now?"^_^
":"T_T
");
}
}
}d;
int main()
{
freopen("2347.in","r",stdin);
freopen("2347.out","w",stdout);
d.Work();
return 0;
}