题目大意：
思路：
网络流最大流
建图：
1.学生编号为11到mm，床编号为m+1m+1到2m2m。 2.将在校学生（无论是否回家）与自己的床相连，边权为1。 3.将在校学生（无论是否回家）的床与结束点TT相连，边权为1。 4.将不回家的学生和来看望的外校同学与起始点SS相连，边权为1。 5.将读入的两两认识的人相连，边权为1。举个栗子（样例）：
第一步：
第二步： 
第三步： 
第四步： 
第五步： 
然后就建好图啦！ 然后就可以找增广路再AC啦！2333 代码：
#include#include #include using namespace std;const int inf=999999999;int k,m,n,x,b[201],c[201][201],f[201][201],t,s,d,sum,tot;struct N{ int zx,ls; //分别表示是否在校和是否留宿}p[201];int dfs(int x) //找增广路{ if (x==t) return 1; //到达了结束点，即找到了一条增广路 for (int i=0;i<=t;i++) //枚举每个点 if (b[i]==-1&&(f[i][x]>0||c[x][i]-f[x][i]>0)) { b[i]=x; if (dfs(i)==1) return 1; } return 0;}void addflow(){ int i; d=inf; i=t; while (i!=s) //找最小边权 { if (c[b[i]][i]>0) d=min(d,c[b[i]][i]-f[b[i]][i]); if (c[i][b[i]]>0) d=min(d,f[i][b[i]]); i=b[i]; } i=t; while (i!=s) //减去最小边权 { if (c[b[i]][i]>0) f[b[i]][i]+=d; if (c[i][b[i]]>0) f[i][b[i]]-=d; i=b[i]; } sum+=d; return;}int main(){ scanf("%d",&k); //多组数据 for (int ___=1;___<=k;___++) { memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); memset(f,0,sizeof(f)); memset(p,0,sizeof(p)); sum=0; tot=0; //初始化 scanf("%d",&m); n=m*2; s=0; t=n+1; //初始化+建图第一步 for (int i=s;i<=t;i++) b[i]=-1; //依旧是初始化 for (int i=1;i<=m;i++) { scanf("%d",&p[i].zx); if (p[i].zx==1) //在校 { c[i][i+m]=1; //第二步 c[i+m][t]=1; //第三步 } } b[s]=0; for (int i=1;i<=m;i++) { scanf("%d",&p[i].ls); if (p[i].ls==0||p[i].zx==0) //留宿或看望 { tot++; c[s][i]=1; //第四步 } } for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) { scanf("%d",&x); if (x==1&&p[j].zx==1) //互相认识 { c[i][j+m]=1; //第五步 } } while (dfs(s)==1) //找增广路 { addflow(); //减去边权 for (int i=s;i<=t;i++) b[i]=-1; b[s]=0; //重新初始化 } if (sum>=tot) puts("^_^"); else puts("T_T"); } return 0;}