题意

有n个同学，给出同学之间的爱慕关系，选出一个集合使得集合中的人没有爱慕关系。问能选出的最大集合是多少。

分析

二分图的最大独立集。

最大独立集的意思是，在图中选出最多的点，使他们两两之间没有边，这个顶点的集合就是最大独立集。

先下结论：如果一个图是二分图，|最大独立集| = |V|-|最大匹配数|。

我们这么思考（设匹配数为\(v\)）：

如果把二分图的最大匹配从原图中去掉，剩下的\(n-2v\)个顶点肯定是没有边相连的（如果还有边相连，我们可以一定可以再加入到匹配中，那还是个锤子的最大匹配）。此时剩下的顶点已经是一个独立集了。接下来，从每条匹配边的两端取一个结点加入独立集中，一定可以使得独立集仍然是独立集：因为对于最大匹配中的任意两个点，要么\(x\)到\(y\)有一条边，要么\(y\)到\(x\)有一条边，要么\(x\)到\(y\)没有边且\(x\)到\(y\)也没有边。这样就能得到这个题目的答案了。

注意：Hungry是针对有向图的，对于无向图match数成了原来的2倍，要除以2。这题除以2的原因和这个还不一样：由于题目没有给出哪些是男的哪些是女的（没有明显的二分图），所以我们是对二分图的两边去进行匹配的（还记得kuangbin的板子吗？在hungary算法中，我们只对一侧进行dfs操作）。所以最大匹配数应该是求出来的数除以2 。

代码

这题的输入格式比较特别，scanf社保之。

#include <iostream>

#include <cstring>

#include <algorithm>

#include <vector>

#define MP make_pair

#define PB push_back

#define fi first

#define se second

#define ZERO(x) memset((x), 0, sizeof(x))

#define ALL(x) (x).begin(),(x).end()

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)

#define per(i, a, b) for (int i = (a); i >= (b); --i)

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

#define MS(x,y) memset(x,y,sizeof(x))

using namespace std;

bool mat[1005][1005];

bool vis[1005];

int link[1005],n;

int dfs(int u)

{

	rep(i,0,n-1)

	{

		if(mat[u][i] && !vis[i])

		{

			vis[i]=true;

			if(link[i]==-1 || dfs(link[i]))

			{

				link[i]=u; return true;

			}

		}

	}

	return false;

}

int hungary()

{

	MS(link,-1);

	int res=0;

	rep(i,0,n-1)

	{

		MS(vis,false);

		if(dfs(i)) res++;

	}

	return res/2;

}

int main()

{

	while(scanf("%d",&n)==1)

	{

		ZERO(mat);

		rep(i,1,n)

		{

			int x, k;

			scanf("%d: (%d)", &x, &k);

			rep(j,1,k)

			{

				int tmp;

				scanf("%d", &tmp);

				mat[x][tmp]=true;

			}

		}

		printf("%d\n", n-hungary());

	}

	return 0;

}

巴特西

「日常训练」Girls and Boys（HDU-1068）

题意

分析

代码

最新文章

热门文章