简单来说，问题就是没回家的学生和外校学生能否和床匹配。这就是一个二分图匹配。
先看如何构建二分图。
如果 x 是学生，那么他可以与他的床匹配
如果 x 认识 y，并且 y 是学生，那么 x 可以与 y 的床匹配。
然后对每一个没有回家和外校的学生进行二分图匹配就行了，如果一个学生没有匹配上，那么就输出"^_^"，如果都匹配输出“T_T”
具体看看代码
#include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> using namespace std; int T,n,stu[55],home[55],mt[55][55],vis[55],nxt[55]; void init(){ memset(mt,0,sizeof(mt)); memset(stu,0,sizeof(stu)); memset(home,0,sizeof(home)); memset(nxt,0,sizeof(nxt)); } bool canMatch(int u){ for(int i=1;i<=n;i++){ if(mt[u][i]&&!vis[i]){ vis[i]=1; if(!nxt[i] || canMatch(nxt[i])){ nxt[i]=u; return true; } } } return false; } int main(){ scanf("%d",&T); while(T--){ init(); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&stu[i]); for(int i=1;i<=n;i++) scanf("%d",&home[i]); for(int i=1;i<=n;i++) if(stu[i]) mt[i][i]=1; //如果i为在校学生那么i可以睡i的床 for(int i=1;i<=n;i++) for(int j=1,x;j<=n;j++){ scanf("%d",&x); if(x && stu[j]) mt[i][j]=1; //如果i认识j并且j在校学生，那么i可以睡j的床 } int flag=1; for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); if((!stu[i] || !home[i]) && !canMatch(i)) {flag=0;break;} //寻找外校学生和不回家的在校学生的匹配 } if(flag==1) printf("^_^ "); else printf("T_T "); } return 0; }