luogu P2055 [ZJOI2009]假期的宿舍

YorkWu

August 22, 2019

1240 views

No comments

375 words

OI 题目

二分图匹配？

可能是我第一道二分图匹配的题吧，反正是前几道，太菜了。。。
我是看的题解，二分图匹配，匈牙利算法。
1. 对于本校学生并且不回家，先直接让他们睡自己的床。
2. 对于外校学生，枚举每一张床，如果他认识这床的主人，那么，第一种情况，没人要预定这张床，他直接睡下即可；第二种情况，这张床已经有人占了，那么就看看预定这张床的人能不能换一张，如果能，就让原来的人走，他留下。

```cpp
#include<bits/stdc++.h>
using namespace std;

struct Solution{
    int T, n;
    vector<int> in, ho, match, book;
    vector<vector<int> > e;

bool dfs(int x){
        for(int i = 1; i <= n; i++){
            if(!book[i] && in[i] && e[x][i] == 1){
                book[i] = 1;
                if(match[i] == 0 || dfs(match[i])){
                    match[i] = x;
                    return 1;
                }
            }
        }
        return 0;
    }

bool work(){
        for(int i = 1; i <= n; i++){
            book = vector<int> (n + 1, 0);
            if((in[i] == 0 || ho[i] == 0) && dfs(i) == 0){
                return 0;
            }
        }
        return 1;
    }

void Solve(){
        scanf("%d", &T);
        while(T--){
            scanf("%d", &n);
            in = vector<int> (n + 1, 0);
            ho = vector<int> (n + 1, 0);
            match = vector<int> (n + 1, 0);
            e.resize(n + 1);
            for(int i = 1; i <= n; i++) e[i].resize(n + 1, 0);
            for(int i = 1; i <= n; i++) scanf("%d", &in[i]);
            for(int i = 1; i <= n; i++) scanf("%d", &ho[i]);
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    scanf("%d", &e[i][j]);
                }
                if(in[i] == 1) e[i][i] = 1;
            }
            if(work()) printf("^_^\n");
            else printf("T_T\n");
        }
    }
};

int main(){
    Solution().Solve();
    return 0;
}
```

Last modification：March 14, 2020