首页 > 代码库 > bzoj1433: [ZJOI2009]假期的宿舍
bzoj1433: [ZJOI2009]假期的宿舍
1433: [ZJOI2009]假期的宿舍
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 2286 Solved: 969
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
1
3
1 1 0
0 1 0
0 1 1
1 0 0
1 0 0
3
1 1 0
0 1 0
0 1 1
1 0 0
1 0 0
Sample Output
ˆ ˆ
HINT
对于30% 的数据满足1 ≤ n ≤ 12。
对于100% 的数据满足1 ≤ n ≤ 50,1 ≤ T ≤ 20。
分析：个人感觉很裸的二分图匹配，题目求是否存在方案，那就是问能不能把要求的人都匹配到床上去,那么利用匈牙利算法即可，如果匹配数等于人的数量，那么就可以匹配，在这里稍微讲一下匈牙利算法,如果1和2匹配，3要和2匹配，但2已经和1匹配了，这个时候让1挪位，1如果可以和4匹配，那么就完美匹配了，如果不行，那么只能匹配一个，所以匈牙利算法主要就是腾位置出来，具体看看代码理解理解吧,多组数据一定要注意初始化！！！
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int maxn = 55;int T,a[maxn][maxn],vis[maxn],ans,bed[maxn],people[maxn],pipei[maxn],n,panduan[maxn],cnt1,cnt2;bool xiongyali(int x){ for (int i = 1; i <= cnt1; i++) if (a[x][bed[i]] && !vis[bed[i]]) { vis[bed[i]] = 1; if (!pipei[bed[i]] || xiongyali(pipei[bed[i]])) { pipei[bed[i]] = x; return true; } } return false;}int main(){ scanf("%d", &T); while (T--) { ans = 0; memset(a, 0, sizeof(a)); memset(bed, 0, sizeof(bed)); memset(panduan, 0, sizeof(panduan)); memset(people, 0, sizeof(people)); memset(pipei, 0, sizeof(pipei)); cnt1 = cnt2 = 0; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &panduan[i]); for (int i = 1; i <= n; i++) { int temp; scanf("%d", &temp); if (panduan[i]) { if (temp) bed[++cnt1] = i; else people[++cnt2] = bed[++cnt1] = i; } else people[++cnt2] = i; } for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]); for (int i = 1; i <= n; i++) if (panduan[i]) a[i][i] = 1; for (int i = 1; i <= cnt2; i++) { memset(vis, 0, sizeof(vis)); if (xiongyali(people[i])) ans++; } if (cnt2 > cnt1) ans = -1; if (ans == cnt2) printf("^_^\n"); else printf("T_T\n"); } return 0;}
bzoj1433: [ZJOI2009]假期的宿舍
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。