记录编号 |
60911 |
评测结果 |
AAAAAAAAAA |
题目名称 |
文理分班 |
最终得分 |
100 |
用户昵称 |
cstdio |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.046 s |
提交时间 |
2013-06-01 11:56:10 |
内存使用 |
0.35 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<deque>
#include<algorithm>
using namespace std;
const int SIZEN=101;
int c[SIZEN][SIZEN]={0};//邻接表
int match[SIZEN]={0};//与哪个匹配
bool abor[SIZEN]={0},home[SIZEN]={0};//abor:是否有床,home:是否回家
bool visit[SIZEN]={0};
//节点下标是1~n
int n,n1,n2;
void read(void){
scanf("%d",&n);
int i,j;
for(i=1;i<=n;i++) scanf("%d",&abor[i]);
for(i=1;i<=n;i++) scanf("%d",&home[i]);
for(i=1;i<=n;i++) visit[i]=false;
for(i=1;i<=n;i++) match[i]=-1;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
c[i][j]=0;
scanf("%d",&c[i][j]);
if(i==j) c[i][j]=1;
if(!abor[j]) c[i][j]=0;
}
}
}
bool findpath(int i){
int j;
for(j=1;j<=n;j++){
if(c[i][j]&&!visit[j]){
visit[j]=true;
if(match[j]==-1||findpath(match[j])){
match[j]=i;
return 1;
}
}
}
return 0;
}
void hungary(void){
bool flag=true;
int i,j;
for(i=1;i<=n;i++){
if(!abor[i]||abor[i]&&!home[i]){
for(j=1;j<=n;j++) visit[j]=false;
if(!findpath(i)){
flag=false;
printf("T_T\n");
return;
}
}
}
printf("^_^\n");
}
int main(){
freopen("divideb.in","r",stdin);
freopen("divideb.out","w",stdout);
int test,i;
scanf("%d",&test);
for(i=1;i<=test;i++){
read();
hungary();
}
return 0;
}