bzoj1433: [ZJOI2009]假期的宿舍（最大二分图匹配）

1433: [ZJOI2009]假期的宿舍

题目：传送门

题解:

　　 这题有点水

　　 跑个二分图匹配就完事了（注意在校生不是一定都互相认识）　

代码：

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#define qread(x)x=read();

using namespace std;

inline int read()

{

    int f=,x=;char ch;

    while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

    return f*x;

}

int a[][];

int T,n,t;

bool v[];

bool b[][];

int f[],k[];

int chw[],match[];

bool find_muniu(int x)

{

    for(int i=;i<=n;i++)

    {

        if(a[x][i] && chw[i]!=t)

        {

            chw[i]=t;

            if(match[i]== || find_muniu(match[i]))

            {

                match[i]=x;

                return true;

            }

        }

    }

    return false;

}

int main()

{

    qread(T);

    while(T--)

    {

        memset(a,false,sizeof(a));

        memset(chw,,sizeof(chw));

        memset(match,,sizeof(match));

        int cnt=;

        qread(n);

        for(int i=;i<=n;i++)qread(v[i]);

        for(int i=;i<=n;i++)

        {

            qread(f[i]);

            if(!v[i] || (v[i] && !f[i]))//如果第i个学生不是在校生，或者是在校生但不回家，那么就需要一个床位

                cnt++;

        }

        for(int i=;i<=n;i++)

        {

            for(int j=;j<=n;j++)

            {

                int x;

                qread(x);

                if(x && ((v[i] && !f[i]) || !v[i]) && v[j])a[i][j]=;

            }

            if(v[i] && !f[i])a[i][i]=;

        }

        int ans=;

        for(int i=;i<=n;i++)

        {

            t=i;

            if(find_muniu(i))ans++;

        }

        if(ans==cnt)printf("^_^\n");

        else printf("T_T\n");

    }

    return ;

}