2014
03-03

# FreeOpen

FreeOpen is an organization which arranges blind data for girls and boys. The moral of that name is “Open your free mind to find your other half”. FreeOpen use a pet to make a match to a girl and a boy. FreeOpen believe that if a girl and a boy like each other and they like the same pet, they will be happy when they are living together with that pet.
There are n boys, m girls and k pets. FreeOpen want know the maximum matches. Each match consists of one girl, one boy and one pet, and each girl, boy or pet can only be in one single match.

The first line consists of an integer T, indicating the number of test cases.
The first line of each case consists of three integers G, B, P, indicating the number of girls, the number of boys and the number of pets. The next G * B matrix indicates whether a girl and a boy like each other. The i-th girl and j-th boy like each other if and only if Matrix (i, j) = 1; the next G * P matrix indicates whether a girl likes a pet and the next B * P matrix indicates whether a boy likes a pet.

The first line consists of an integer T, indicating the number of test cases.
The first line of each case consists of three integers G, B, P, indicating the number of girls, the number of boys and the number of pets. The next G * B matrix indicates whether a girl and a boy like each other. The i-th girl and j-th boy like each other if and only if Matrix (i, j) = 1; the next G * P matrix indicates whether a girl likes a pet and the next B * P matrix indicates whether a boy likes a pet.

2
2 1 3
1
1
1 1 1
1 1 1
0 0 0
15 15 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

0
13

Freeopen

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MIN(x,y) (x<y?x:y)

int g,b,p;
int G,B,P;
int gdeg[22];
int grank[22];
int gb[22],gp[22],bp[22];
bool in(){
char c=getchar();
while(c<=32) c=getchar();
return (c=='1');
}

int vis;
int mat[22];
inline bool find0(int u){
for(int i=0;i<b;i++){
if(B&(1<<i)) continue;
if(!(gb[u]&(1<<i))) continue;
if(vis&(1<<i)) continue;
vis|=(1<<i);
if(mat[i]==-1||find0(mat[i])){
mat[i]=u;
return true;
}
}
return false;
}

inline bool find1(int u){
for(int i=0;i<p;i++){
if(P&(1<<i)) continue;
if(!(gp[u]&(1<<i))) continue;
if(vis&(1<<i)) continue;
vis|=(1<<i);
if(mat[i]==-1||find1(mat[i])){
mat[i]=u;
return true;
}
}
return false;
}

inline bool find2(int u){
for(int i=0;i<p;i++){
if(P&(1<<i)) continue;
if(!(bp[u]&(1<<i))) continue;
if(vis&(1<<i)) continue;
vis|=(1<<i);
if(mat[i]==-1||find2(mat[i])){
mat[i]=u;
return true;
}
}
return false;
}

int dep;
inline bool h(int d,int tg){
int cnt=0;
memset(mat,-1,sizeof(mat));
for(int i=tg;i<g;i++){
vis=0;
if(find0(grank[i])) cnt++;
if(cnt>dep-d) break;
}
if(cnt+d<dep) return false;

cnt=0;
memset(mat,-1,sizeof(mat));
for(int i=tg;i<g;i++){
vis=0;
if(find1(grank[i])) cnt++;
if(cnt>dep-d) break;
}
if(cnt+d<dep) return false;

cnt=0;
memset(mat,-1,sizeof(mat));
for(int i=0;i<b;i++){
if(B&(1<<i)) continue;
vis=0;
if(find2(i)) cnt++;
if(cnt>dep-d) break;
}
if(cnt+d<dep) return false;

return true;
}

bool dfs(int d,int tg){
if(d==dep) return true;
if(!h(d,tg)) return false;

for(int ii=tg;ii<g;ii++){
int i=grank[ii];
G|=(1<<i);
for(int j=0;j<b;j++){
if(B&(1<<j)) continue;
if(!(gb[i]&(1<<j))) continue;
B|=(1<<j);
for(int k=0;k<p;k++){
if(P&(1<<k)) continue;
if(gp[i]&bp[j]&(1<<k)){
P|=(1<<k);
if(dfs(d+1,ii+1)) return true;
P^=(1<<k);
}
}
B^=(1<<j);
}
G^=(1<<i);
}
return false;
}

bool gcmp(const int& a,const int& b){
return gdeg[a]<gdeg[b];
}

int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&g,&b,&p);
memset(gb,0,sizeof(gb));
memset(gp,0,sizeof(gp));
memset(bp,0,sizeof(bp));
memset(gdeg,0,sizeof(gdeg));
for(int i=0;i<g;i++){
for(int j=0;j<b;j++){
gb[i]|=(in()<<j);
}
}
for(int i=0;i<g;i++){
for(int j=0;j<p;j++){
gp[i]|=(in()<<j);
}
}
for(int i=0;i<b;i++){
for(int j=0;j<p;j++){
bp[i]|=(in()<<j);
}
}

for(int i=0;i<g;i++){
grank[i]=i;
for(int j=0;j<b;j++){
if(!(gp[i]&bp[j])) gb[i]&=~(1<<j);
if(gb[i]&(1<<j)) gdeg[i]++;
}
}
sort(grank,grank+g,gcmp);
//reverse(grank,grank+g);

G=B=P=0;
dep=MIN(MIN(g,b),p);
while(true){
if(dfs(0,0)) break;
dep--;
}

printf("%d\n",dep);
}
}

1. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.