题解 | #[ZJOI2009]假期的宿舍#

[ZJOI2009]假期的宿舍

题目描述：

学校放假了，有些同学放假回家了，有些同学不回家，而不回家的同学的非本校的朋友要到学校和他一起搞基，但是非本校的学生没有床位，这就需要进行床位转借，人总是会睡自己或自己认识的人的床，问能否存在一个方案使得所有不回家的学生和来和他们搞基的学生都有地方住

思路：

二分图

找出左集合，和右集合，然后连边，跑匈牙利就可以

左集合是需要住的人，右集合是床位

需要住的就是不回家的所有人，床位是所有本校的人

这里就用两个vis数组标记一下，左集合就在去dfs之前判断一下，如果这个人需要住宿，那就去dfs，右集合就在dfs里面的找床位的时候判断一下，看看当前这个人有没有床位

其他的和普通的匈牙利差不多

多组输入，记得初始化

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX  50 + 50
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!提交不看数据范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int t, n, x, num;
bool vis1[MAX], vis2[MAX];
int tr[MAX][MAX];
bool vis[MAX];
int link[MAX];

bool dfs(int x){
    for(int i = 1; i <= n; ++i){
        if(vis1[i]){//判断这个人有没有床位
            if(!vis[i] && tr[x][i]){
                vis[i] = 1;
                if(!link[i] || dfs(link[i])){
                    link[i] = x;
                    return true;
                }
            }
        }
    }
    return false;
}

void work(){
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        if(!vis2[i]){//判断这个人需不需要住校
            mem(vis, 0);
            if(dfs(i))++ans;
        }
    }
    if(ans == num)cout<<"^_^\n";
    else cout<<"T_T\n";
}

int main(){
    sd(t);
    while (t--) {
        num = 0;
        mem(link, 0);
        mem(vis1, 0);//在校否 
        mem(vis2, 0);//回家否 
        sd(n);
        for(int i = 1; i <= n; ++i){
            cin>>x;
            if(x)vis1[i] = 1;
        }
        for(int i = 1; i <= n; ++i){
            cin>>x;
            if(vis1[i] && x == 1){
                vis2[i] = 1;
                ++num;
            }
        }
        num = n - num;//住校的人的个数
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                cin>>tr[i][j];
            }
            tr[i][i] = 1;
        }
        work();
    }
    return 0;
}