洛谷P2055假期的宿舍

题目

此题主要是考察二分图匹配，而二分图匹配最主要的就是建图，而图一般都是要分成两个部分来分，比如该题就需要先将在学校住的人和床连在一起，因为在学校住就会与一个床。然后每两个人之间假如他们相互认识就可以相互连边，这样就可以通过人人相连实现人床相连。

\(Code\)

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

#pragma GCC optimize(2)

#pragma GCC optimize(3)

using namespace std;

int n1, T, cnt;

int map[1010][1010];

int vis[200100], lin[200010], school[200100], home[200010], flag[200100];

struct cym {

    int to, nex;

}e[200010];

inline void add(int f, int t)

{

    e[++cnt].to = t;

    e[cnt].nex = lin[f];

    lin[f] = cnt;

}

inline bool dfs(int now)

{

    for (int i = lin[now]; i; i = e[i].nex)

        if (!vis[e[i].to])

        {

            vis[e[i].to] = 1;

            if (!flag[e[i].to] || dfs(flag[e[i].to])) {

                flag[e[i].to] = now; return true;

            }

        }

    return false;

}

int main()

{

    scanf("%d", &T);

    while (T--)

    {

        int ans = 0, sum = 0;

        memset(map, 0, sizeof(map)); memset(school, 0, sizeof(school));memset(home, 0, sizeof(home));memset(flag, 0, sizeof(flag));memset(e, 0, sizeof(e));memset(lin, 0, sizeof(lin));

        cnt = 0;

		scanf("%d", &n1);

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

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

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

        {

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

            if (!school[i])

            	home[i] = 0;

            if (school[i])

                add(i, i);

        }

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

        	if (!home[i])

        		sum++;

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

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

            {

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

                if (map[i][j] && school[j])

                    add(i, j);

            }

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

            if (!home[i])

            {

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

                if (dfs(i)) ans++;

            }

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

        else printf("T_T\n");

    }

    return 0;

}

/*

2

3

1 1 0

0 1 0

0 0 1

0 0 0

1 0 0

3

1 1 0

0 1 0

0 1 1

1 0 0

1 0 0

*/