这道题开始感觉不出是二分图最大匹配的qwq。但是今天学了匈牙利算法，想来做几个题qwq。做这个题的时候想了很久它哪里是二分图，脑子里是“两列，每列有很多点的那种图 qwq。”
然后看了题解，发现竟是这样简单qwq。
关键还在建图。
首先把本校且不回家的学生自己向自己连一条边，之后再把和自己认识的还是本校的学生连一条边（不用管他回不回家），之后跑一遍最大匹配就成了。
回顾一下我们发现，它确实满足“任意两条边没有公共端点”的性质，因为我们暂时排除了基♂的情况，不会有两个人睡在一张床上。
然后注意在主程序中跑匹配的时候，不是每个点都跑，而是那些有住宿需求的人跑。（为此WA了两次qwq）
Code
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 int T,n,sta,ans,tot; 8 int stu[100],head[100],home[100],match[100]; 9 bool vis[100];10 struct node{11 int to,next;12 }edge[10000];13 14 void add(int x,int y)15 {16 edge[++tot].to=y;17 edge[tot].next=head[x];18 head[x]=tot;19 }20 21 bool dfs(int x)22 {23 for(int i=head[x];i;i=edge[i].next)24 {25 int y=edge[i].to;26 if(!vis[y])27 {28 vis[y]=1;29 if(!match[y]||dfs(match[y]))30 {31 match[y]=x;32 return 1;33 }34 }35 }36 return 0;37 }38 39 int main()40 {41 scanf("%d",&T);42 while(T--)43 {44 scanf("%d",&n);45 for(int i=1;i<=n;i++) scanf("%d",&stu[i]);46 for(int i=1;i<=n;i++)47 {48 if(stu[i]) scanf("%d",&home[i]);49 else scanf("%d",&home[0]);50 if(!home[i]&&stu[i]) add(i,i);51 } 52 for(int i=1;i<=n;i++)53 for(int j=1;j<=n;j++)54 {55 int x=0;56 scanf("%d",&x);57 if(x&&stu[j]) add(i,j);58 }59 for(int i=1;i<=n;i++)60 if(!stu[i]||(!home[i]&&stu[i])) sta++; 61 for(int i=1;i<=n;i++)62 if(!stu[i]||(!home[i]&&stu[i]))63 {64 memset(vis,0,sizeof(vis));65 if(dfs(i)) ans++;66 }67 if(ans==sta) printf("^_^\n");68 else printf("T_T\n");69 memset(match,0,sizeof(match));70 memset(head,0,sizeof(head));71 sta=0,ans=0,tot=0;72 }73 return 0;74 }