bzoj 1433 //1433:[ZJOI2009]假期的宿舍 //在线测评地址https://www.lydsy.com/JudgeOnline/problem.php?id=1433
更多题解，详见https://blog.csdn.net/mrcrack/article/details/90228694BZOJ刷题记录
二分图小白，建议学习https://blog.csdn.net/dark_scope/article/details/8880547二分图算法，此文介绍得相当棒
刷刷模版题https://www.luogu.org/problem/P3386 P3386 【模板】二分图匹配 再开始下面内容的学习．2019-10-2 21:26
bzoj 1433
832 kb92 msC++/Edit1555 B洛谷46ms / 800.00KB / 1.04KB C++
//1433:[ZJOI2009]假期的宿舍 //二分图 //构图是关键 //boy要睡学校的学生 bed床 //样例通过，提交0分，全WA．2019-10-2 16:57 //在AC的代码上修改，逐渐逼近全WA的代码，提交了18次，才发现，是矩阵数组读取有误,
//查了好久好久．10-02 16:07:20查到10-02 19:38:38 //明明是一个完整矩阵，却按上三角矩阵进行读取，错误代码如下 /* for(i=1;i<=n;i++) for(j=i+1;j<=n;j++){ scanf("%d",&v); if(v==1){ if(map[i][i])map[j][i]=1;//j可睡i床 if(map[j][j])map[i][j]=1;//i可睡j床 } } */ //提供一组测试数据给读者 /* 1 12 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1
0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0
T_T */ //样例通过，提交AC.2019-10-2 21:17 #include <stdio.h> #include <string.h> #define maxn 55 int map[maxn][maxn],n,boy[maxn]; int used[maxn],link[maxn],bed[maxn]; void init(){ int i,v,j; memset(map,0,sizeof(map)),memset(boy,0,sizeof(boy)),memset(bed,0,sizeof(bed)); for(i=1;i<=n;i++){ scanf("%d",&v); if(v==1)bed[i]=1; } for(i=1;i<=n;i++){ scanf("%d",&v); if(bed[i]) if(v==1)boy[i]=1;//i在校学生，回家 } for(i=1;i<=n;i++){//之前读取矩阵写错，查了好久好久．10-02 16:07:20查到10-02 19:38:38 for(j=1;j<=n;j++) scanf("%d",&map[i][j]); map[i][i]=1; } } int find(int u){ int i; for(i=1;i<=n;i++) if(bed[i]&&map[u][i]&&!used[i]){ used[i]=1; if(!link[i]||find(link[i])){ link[i]=u; return 1; } } return 0; } void solve(){ int i; memset(link,0,sizeof(link)); for(i=1;i<=n;i++){ if(boy[i])continue; memset(used,0,sizeof(used));//漏了此行 if(find(i)); else break; } if(i==n+1)printf("^_^\n");//此处错写成if(i==n+1)printf("^_^"); else printf("T_T\n");//此处错写成else printf("T_T"); } int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d",&n); init(); solve(); } return 0; }
