BZOJ 1433 && Luogu P2055 [ZJOI2009]假期的宿舍 匈牙利算法

刚学了匈牙利正好练练手（我不会说一开始我写错了）（怕不是寒假就讲了可是我不会）

把人看做左部点，床看作右部点

建图：（！！在校相当于有床，不在校相当于没有床 但是要来学校）

　　1.在校的 不走的人 自己和自己的床连边；

　　2.不在校的人或在校不回家的人 和 认识的 并且 在校的人 的床 连边；

于是统计一下需要几张床，再跑匈牙利算法、、、看看够不够。

#include<cstdio>

#include<iostream>

#include<cstring>

#define R register int

using namespace std;

inline int g() {

    R ret=; register char ch; while(!isdigit(ch=getchar()));

    do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret;

}

int t,n,cnt,ans,tot;

int vr[],nxt[],fir[],pre[];

inline void add(int u,int v) {vr[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt;}

bool vis[],h[],s[];

bool dfs(int u) {

    for(R i=fir[u];i;i=nxt[i]) {R v=vr[i];

        if(vis[v]) continue; vis[v]=true;

        if(!pre[v]||dfs(pre[v])) {pre[v]=u; return true;}

    } return false;

}

signed main() {

    t=g();

    while(t--) { cnt=tot=ans=;

        memset(pre,,sizeof(pre)),memset(fir,,sizeof(fir)),memset(nxt,,sizeof(nxt)),memset(vr,,sizeof(vr));

        n=g(); for(R i=;i<=n;++i) s[i]=g();

        for(R i=;i<=n;++i) {

            h[i]=g(); if(!h[i]&&s[i]) add(i,i+n),add(i+n,i);

        }

        for(R i=;i<=n;++i) for(R j=,x;j<=n;++j) {

            x=g();

            if(x&&i!=j) {

                if(s[j]&&((s[i]&&!h[i])||!s[i])) add(i,j+n),add(j+n,i);

                if(s[i]&&((s[j]&&!h[j])||!s[j])) add(j,i+n),add(i+n,j);

            }

        }

        for(R i=;i<=n;++i) if(!s[i]||(s[i]&&!h[i])) ++tot;

        for(R i=;i<=n;++i) if(!s[i]||(s[i]&&!h[i])) {

            memset(vis,,sizeof(vis)); ans+=dfs(i);

        } ans==tot?printf("^_^\n"):printf("T_T\n");

    }

}

然而有种更厉害的建图，但是我不会。。。哪位大佬给讲讲QAQ，如下：

#include<cstdio>

#include<iostream>

#include<cstring>

#define R register int

using namespace std;

inline int g() {

    R ret=; register char ch; while(!isdigit(ch=getchar()));

    do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret;

}

int t,n,cnt,ans,tot;

int vr[],nxt[],fir[],pre[];

inline void add(int u,int v) {vr[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt;}

bool vis[],h[],s[];

bool dfs(int u) {

    for(R i=fir[u];i;i=nxt[i]) {R v=vr[i];

        if(vis[v]) continue; vis[v]=true;

        if(!pre[v]||dfs(pre[v])) {pre[v]=u; return true;}

    } return false;

}

signed main() {

    t=g();

    while(t--) { cnt=tot=ans=;

        memset(pre,,sizeof(pre)),memset(fir,,sizeof(fir)),memset(nxt,,sizeof(nxt)),memset(vr,,sizeof(vr));

        n=g(); for(R i=;i<=n;++i) s[i]=g();

        for(R i=;i<=n;++i) {

            h[i]=g(); if(!h[i]&&s[i]) add(i,i);

        }

        for(R i=;i<=n;++i) for(R j=,x;j<=n;++j) {

            x=g(); if(x&&s[j]) add(i,j);

        }

        for(R i=;i<=n;++i) if(!s[i]||(s[i]&&!h[i])) ++tot;

        for(R i=;i<=n;++i) if(!s[i]||(s[i]&&!h[i])) {

            memset(vis,,sizeof(vis)); ans+=dfs(i);

        } ans==tot?printf("^_^\n"):printf("T_T\n");

    }

}

---

2019.04.14