[ZJOI2009]假期的宿舍 二分图匹配匈牙利

[ZJOI2009]假期的宿舍 二分图匹配匈牙利

一个人对应一张床，每个人对床可能不止一种选择，可以猜出是二分图匹配。

床只能由本校的学生提供，而需要床的有住校并且本校和外校两种人。最后统计二分图匹配对数是否等于需要的床数即可。

注意细节，认真审题。

#include <cstdio>
#include <cstring>
#define MAXN 100
using namespace std;
int head[MAXN],nxt[10000],vv[10000],tot;
inline void add_edge(int u, int v){
    vv[++tot]=v;
    nxt[tot]=head[u];
    head[u]=tot;
}
bool ins[MAXN],home[MAXN];
int n,want;
void init(){
    memset(ins, 0, sizeof(ins));
    memset(home, 0, sizeof(home));
    memset(head, 0, sizeof(head));
    memset(nxt, 0, sizeof(nxt));
    memset(vv, 0, sizeof(vv));
    tot=0;
    want=0;
}
bool vis[MAXN];
int m[MAXN];
bool dfs(int u){
    for(int i=head[u];i;i=nxt[i]){
        int v=vv[i];
        if(vis[v]) continue;
        vis[v]=1;
        if(m[v]==0||dfs(m[v])){
            m[v]=u;
            return 1;
        }
    }
    return 0;
}
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        init();
        for(int i=1;i<=n;++i) scanf("%d", &ins[i]);
        for(int i=1;i<=n;++i){
            scanf("%d", &home[i]);
            if(ins[i]&&home[i]==0) add_edge(i, i);
        }
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j){
                int t;scanf("%d", &t);
                if(t==1&&ins[j]) add_edge(i, j);
            }
        memset(m, 0, sizeof(m));
        int ans=0;
        for(int i=1;i<=n;++i)
            if(!ins[i]||(ins[i]&&home[i]==0)){
                ++want;
                memset(vis, 0, sizeof(vis));
                if(dfs(i)) ++ans;
            }
        //printf("%d
%d", want, ans);
        if(ans==want) printf("^_^
");
        else printf("T_T
");
    }
    return 0;
}