BZOJ1433_假期的宿舍_KEY

题目传送门

二分图匹配的题目。

但建边有一定难度，关系比较复杂。

首先要统计总共需要几张床。

在校且住校的会需要一张床，不住校的需要一张床。

然后对于在校且住校的与自己的床连边，不住校的与认识的住校的人连一条边。

跑一遍匈牙利就好了。

code：

/**************************************************************

    Problem: 1433

    User: yekehe

    Language: C++

    Result: Accepted

    Time:28 ms

    Memory:824 kb

****************************************************************/

#include <cstdio>

#include <vector>

#include <cstring>

using namespace std;

int read()

{

    char c;while(c=getchar(),c<''||c>'');

    int x=c-'';while(c=getchar(),c>=''&&c<='')x=x*+c-'';

    return x;

}

int T,N,o,cnt,ans;

int k[],w[];

vector<int>a[];

int vis[],last[],now;

bool find(int x)

{

    for(int i=;i<a[x].size();i++){

        int to=a[x][i];

        if(vis[to]!=now){

            vis[to]=now;

            if(!last[to] || find(last[to])){

                last[to]=x;

                return true;

            }

        }

    }

    return false;

}

int main()

{

    T=read();

    register int i,j;

        while(T--){

            ans=cnt=;

            N=read();

            memset(last,,sizeof last);

            memset(a,,sizeof a);

                for(i=;i<=N;i++)k[i]=read();

                for(i=;i<=N;i++)w[i]=read();

                for(i=;i<=N;i++){

                    if(!k[i])cnt++;

                    else {

                        if(!w[i])cnt++,a[i].push_back(i);

                    }//建边且统计床的数量

                }

                for(i=;i<=N;i++)

                    for(j=;j<=N;j++){

                        o=read();

                        if(!o)continue;

                        if(k[j])a[i].push_back(j);//建边

                    }

                for(i=;i<=N;i++)

                    if(!k[i]||!w[i])now++,ans+=find(i);//二分图匹配

            puts(ans==cnt?"^_^":"T_T");

        }

    return ;

}