我觉得二分图的难点就是在建图的思想上。对于这道题，同样是需要将题中的条件进行建图。理一下思路，看一下可以怎样转化：
1.每个在学校的学生肯定可以睡自己的床，所以就自己向自己连边。
2.每个人（不管在或不在学校，是不是学生）都可以睡自己认识的人的床。
这两个条件还是挺好想的。然后就统计一下有多少需要的床，跑一遍二分图最大匹配，看是否满足条件即可。
代码如下：
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; const int N=550; int school[maxn]; int home[maxn]; int n,t; int relation[N][N]; bool vis[maxn]; int match[maxn]; struct node{ int nxt,to; }edge[maxn*2]; int head[maxn],cnt; void add(int x,int y){ edge[++cnt].nxt=head[x]; edge[cnt].to=y; head[x]=cnt; } int ans,bed; bool dfs(int x){ for(int i=head[x];i;i=edge[i].nxt){ int v=edge[i].to; if(!vis[v]){ vis[v]=true; if(!match[v]||dfs(match[v])){ match[v]=x; return true; } } } return false; } int main(){ scanf("%d",&t); while(t--){ memset(match,0,sizeof(match)); memset(head,0,sizeof(head)); memset(vis,false,sizeof(vis)); scanf("%d",&n); ans=0,bed=0,cnt=0; for(int i=1;i<=n;i++) scanf("%d",&school[i]); for(int i=1;i<=n;i++){ scanf("%d",&home[i]); if(!home[i]&&school[i]){ //cout<<i<<" "<<i<<endl; add(i,i); } //自己和自己的床位连边。 } for(int i=1;i<=n;i++){ if((!home[i]&&school[i])||!school[i]) bed++; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%d",&relation[i][j]); if(relation[i][j]&&school[j]){ //cout<<i<<" "<<j<<endl; add(i,j); } } } for(int i=1;i<=n;i++){ if((school[i]&&!home[i])||!school[i]){ memset(vis,false,sizeof(vis)); if(dfs(i)) ans++; } } if(ans>=bed) printf("^_^ "); else printf("T_T "); } return 0; }