二分图匹配?

可能是我第一道二分图匹配的题吧,反正是前几道,太菜了。。。
我是看的题解,二分图匹配,匈牙利算法。

  1. 对于本校学生并且不回家,先直接让他们睡自己的床。
  2. 对于外校学生,枚举每一张床,如果他认识这床的主人,那么,第一种情况,没人要预定这张床,他直接睡下即可;第二种情况,这张床已经有人占了,那么就看看预定这张床的人能不能换一张,如果能,就让原来的人走,他留下。
#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 14th, 2020 at 09:14 pm