bzoj1433: [ZJOI2009]假期的宿舍

2022-08-16 14:33:46

1433: [ZJOI2009]假期的宿舍

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2286 Solved: 969
[Submit][Status][Discuss]

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。

分析：个人感觉很裸的二分图匹配，题目求是否存在方案，那就是问能不能把要求的人都匹配到床上去,那么利用匈牙利算法即可，如果匹配数等于人的数量，那么就可以匹配，在这里稍微讲一下匈牙利算法,如果1和2匹配，3要和2匹配，但2已经和1匹配了，这个时候让1挪位，1如果可以和4匹配，那么就完美匹配了，如果不行，那么只能匹配一个，所以匈牙利算法主要就是腾位置出来，具体看看代码理解理解吧,多组数据一定要注意初始化！！！

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 55;

int T,a[maxn][maxn],vis[maxn],ans,bed[maxn],people[maxn],pipei[maxn],n,panduan[maxn],cnt1,cnt2;

bool xiongyali(int x)

{

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

        if (a[x][bed[i]] && !vis[bed[i]])

        {

        vis[bed[i]] = 1;

        if (!pipei[bed[i]] || xiongyali(pipei[bed[i]]))

        {

            pipei[bed[i]] = x;

            return true;

        }

        }

    return false;

}

int main()

{

    scanf("%d", &T);

    while (T--)

    {

        ans = 0;

        memset(a, 0, sizeof(a));

        memset(bed, 0, sizeof(bed));

        memset(panduan, 0, sizeof(panduan));

        memset(people, 0, sizeof(people));

        memset(pipei, 0, sizeof(pipei));

        cnt1 = cnt2 = 0;

        scanf("%d", &n);

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

            scanf("%d", &panduan[i]);

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

        {

            int temp;

            scanf("%d", &temp);

            if (panduan[i])

            {

                if (temp)

                    bed[++cnt1] = i;

                else

                    people[++cnt2] = bed[++cnt1] = i;

            }

            else

                people[++cnt2] = i;

        }

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

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

                scanf("%d", &a[i][j]);

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

            if (panduan[i])

                a[i][i] = 1;

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

        {

            memset(vis, 0, sizeof(vis));

            if (xiongyali(people[i]))

                ans++;

        }

        if (cnt2 > cnt1)

            ans = -1;

        if (ans == cnt2)

            printf("^_^\n");

        else

            printf("T_T\n");

    }

    return 0;

}

码农公寓