bzoj 1433: [ZJOI2009]假期的宿舍

1433: [ZJOI2009]假期的宿舍

Description

Input

Output

Sample Input

1
3
1 1 0
0 1 0
0 1 1
1 0 0
1 0 0

Sample Output

ˆ_ˆ

HINT

对于30% 的数据满足1 ≤ n ≤ 12。
对于100% 的数据满足1 ≤ n ≤ 50,1 ≤ T ≤ 20。

题解：

很显然的二分图最大匹配，先算出有几个人要住校，然后跑一遍匹配判断一下即可。。

连边注意一下就好了。。

#include<stdio.h>

#include<iostream>

using namespace std;

const int N=55;

int T,i,j,n,cnt,ans,f[N],p[N],b[N],c[N],a[N][N];

inline void read(int &v){

    char ch,fu=0;

    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());

    if(ch=='-') fu=1, ch=getchar();

    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';

    if(fu) v=-v;

}

int dfs(int x,int M)

{

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

        if(a[x][i]==1)

    {

        if(p[i]==M) continue;

        p[i]=M;

        if(f[i]==0||dfs(f[i],M))

        {

            f[i]=x;

            return 1;

        }

    }

    return 0;

}

int main()

{

    read(T);

    while(T--)

    {

        read(n);

        for(i=1;i<=n;i++) read(b[i]);

        cnt=0;

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

        {

            read(c[i]);

            if(b[i]==0||(b[i]==1&&c[i]==0)) cnt++;

        }

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

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

        {

            read(a[i][j]);

            if(i==j&&b[i]==1&&c[i]==0) a[i][j]=1;else

            {

                if((b[i]==0||b[i]==1&&c[i]==0)&&a[i][j]&&b[j]==1) a[i][j]=1;else

                a[i][j]=0;

            }

        }

        ans=0;

        for(i=1;i<=n;i++) p[i]=f[i]=0;

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

            ans+=dfs(i,i);

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

    }

    return 0;

}