原题链接：https://www.luogu.org/problem/show?pid=2055

其实本题除了建边之外几乎与二分图最大匹配模板题没什么区别。

二分图的一边的人，一边为床。。。

如果本校学生且回家，那么就没他什么事情了，他并不需要床铺。如果是本校学生但不回家，那么就可以向自己的床连一条边，因为下面的邻接矩阵中并没有给出这种方案，但它是存在的。外校学生的话，就要向自己认识的人的床连一条边。

之后跑二分图最大匹配即可，检查匹配数是否能满足需求。

本题有多组数据，一定记得把head，tot，cnt这些东西清空。不然就会像我在后面的几组数据中WA到怀疑人生。

 

#include
     
      #include
      
       void read(int &y){    y=0;char x=getchar();    while(x<'0'||x>'9') x=getchar();    while(x>='0'&&x<='9')    {        y=y*10+x-'0';        x=getchar();    }}struct edge{    int u,v;}e[10005];int t,n,tot,sum,x,cnt;int d[55],z[55];int vis[105],head[105],match[105];void add(int u,int v){    e[++cnt].u=head[u];    e[cnt].v=v;    head[u]=cnt;}int dfs(int x){    for(int i=head[x];i;i=e[i].u)    {        int t=e[i].v;        if(vis[t]==1) continue;        vis[t]=1;        if(match[t]==0||dfs(match[t]))        {            match[t]=x;            return 1;        }     }    return 0;}int main(){    read(t);    while(t--)    {        read(n);        memset(head,0,sizeof(head));cnt=0;tot=0;//WA WA WA        for(int i=1;i<=n;i++) read(d[i]);        for(int i=1;i<=n;i++)        {            read(z[i]);            if(z[i]==0&&d[i]==1) add(i,i);            if(d[i]==0||(z[i]==0&&d[i]==1)) tot++;        }        for(int i=1;i<=n;i++)        {            for(int j=1;j<=n;j++)            {                read(x);                if(x==1&&d[j]==1) add(i,j);            }        }        memset(match,0,sizeof(match));        sum=0;        for(int i=1;i<=n;++i)        {            if((d[i]==1&&z[i]==0)||d[i]==0)            {                memset(vis,0,sizeof(vis));                if(dfs(i)) sum++;            }        }        if(sum>=tot) printf("^_^\n");        else printf("T_T\n");    }    return 0;}