题目链接：

https://www.luogu.org/problemnew/show/P2055

分析：

这道题比较简单，二分图的练习题（当然最大流同理）。

易得我们可以将人放在一侧，床放在一侧。

A与B认识就互相向对方的床连边流量为1

A不回家则S向A连流量为1的边。

A有床则向T连流量为1的边。

跑最大流即可。

最后判断是否等于不回家的人数。

然鹅因为作者较懒，于是写了二分图，大家可以两种方法都看看。

代码：

#include<cstdio>

#include<vector>

#include<cstring>

using namespace std;

vector<int>v[20005];

int vis[20005],link[20005];

int t;

int a[55],b[55];

int find(int x)

{

    for(int i=0;i<v[x].size();i++)

    {

        int p=v[x][i];

        if(vis[p]!=t)

        {

            vis[p]=t;

            if((!link[p])||find(link[p]))

            {

                link[p]=x;

                return 1;

            }

        }

    }

    return 0;

}

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		memset(link,0,sizeof(link));

		int n;

		scanf("%d",&n);

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

		{

			v[i].clear();

		}

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

		{

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

		}

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

		{

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

			if(b[i]==0&&a[i])

			{

				v[i].push_back(i);

			}

		}

		int cnt=0;

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

		{

			if(!a[i]||(a[i]&&!b[i]))

			cnt++;

		}

		int tmp;

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

		{

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

			{

				scanf("%d",&tmp);

				if(tmp&&a[j])

				{

					v[i].push_back(j);

				}

			}

		}

		int tot=0;

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

		{

			if((a[i]&&!b[i])||!a[i])

			{

			t++;

			if(find(i))

			{

				tot++;

			}

			//else

			//break;

			}

		}

		if(tot==cnt)

		{

			printf("^_^\n");

		}

		else

		printf("T_T\n");

	}

	return 0;

}

巴特西

洛谷P2055 [ZJOI2009]假期的宿舍题解

题目链接：

分析：

然鹅因为作者较懒，于是写了二分图，大家可以两种方法都看看。

代码：

最新文章

热门文章

巴特西

洛谷P2055 [ZJOI2009]假期的宿舍 题解

题目链接：

分析：

然鹅因为作者较懒，于是写了二分图，大家可以两种方法都看看。

代码：

最新文章

热门文章

洛谷P2055 [ZJOI2009]假期的宿舍题解