Linux安全网 - Linux操作系统_Linux 命令_Linux教程_Linux黑客

绿色网站无广告
会员投稿 投稿指南 本期推荐:
搜索:
您的位置: Linux安全网 > Linux编程 > » 正文

HDU-1068 Girls and Boys

来源: niushuai666 分享至:

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1068

题目大意:

现在由N个同学,他们之间可能有一定的浪漫关系,给出存在浪漫关系的同学。现在一个研究者要找出一个最大的同学的集合,这个集合满足的条件是:任意两个同学都没有浪漫关系。求这个集合的最大人数。

解题思路:

二分图的最大独立集。

但是这道题有一点不同,它没有告诉我们是男生还是女生,所以我们需要进行拆点,把一个学生拆成一个男生和一个女生,然后求出最大匹配后除以2即可。


最大独立集是指在一个有N个顶点的图G中,选出m个点,这m个点任意2个点都没有边相连。二分图最大匹配是含有最大匹配数目的子图,一个匹配含有2个顶点,那么有2*最大匹配最大匹配含个顶点。

最大独立集 = 顶点数 - 2 * 最大匹配 + 最大匹配

先减去已经匹配的顶点数,共2 * 最大匹配个,然后发现对于最大匹配,在一边的点是不可能有边相连的,所以要加上一边的点,所以:

二分图最大独立集=顶点数  —  二分图最大匹配。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
using namespace std;
#define M 510
#define N 250010
int Head[M], Next[N], Key[N];
int match[M];
bool use[M];
int num;
int n;

void add(int u, int v)
{
	Key[num] = v;
	Next[num] = Head[u];
	Head[u] = num++;
}

bool find(int u)
{
	int temp;
	for(int i = Head[u]; i != -1; i = Next[i])
	{
		temp = Key[i];
		if(!use[temp])
		{
			use[temp] = true;
			if(match[temp] == -1 || find(match[temp]))
			{
				match[temp] = u;
				return true;
			}
		}
	}
	return false;
}

int hungary()
{
	int sum = 0;
	for(int i = 0; i < n; ++i)
	{
		memset(use, false, sizeof(use));
		if(find(i))
			sum++;
	}
	return sum;
}

int main()
{
	int u, allnum, v;
	while(scanf("%d", &n) != EOF)
	{
		num = 0;
		memset(match, -1, sizeof(match));
		memset(Head, -1, sizeof(Head));
		for(int i = 0; i < n; ++i)
		{
			scanf("%d: (%d)", &u, &allnum);
			for(int j = 0; j < allnum; ++j)
			{
				scanf("%d", &v);
				add(u, v);
			}
		}
		printf("%d\n", n - hungary() / 2);
	}
	return 0;
}


Tags:
分享至:
最新图文资讯
1 2 3 4 5 6
验证码:点击我更换图片 理智评论文明上网,拒绝恶意谩骂 用户名:
关于我们 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 发展历史