当前位置: 代码迷 >> 综合 >> POJ 1466 Girls and Boys (挑战程序设计竞赛,二分图最大独立集)
  详细解决方案

POJ 1466 Girls and Boys (挑战程序设计竞赛,二分图最大独立集)

热度:8   发布时间:2023-12-13 19:29:02.0

挑战程序设计竞赛,283页,二分图最大独立集
二分图的最大独立集
题目意思:
在一群男女生之间存在浪漫关系,且只存在于男女之间,现给出存在关系的人的编号,但没给具体的男女性别,
现在要求一个集合,在集合中任意两人都不存浪漫关系,输出集合中元素的个数.

本题要点:
1、定理:
二分图的最大独立集 = 总点数 - 最大匹配数
2、这里采用邻接表来存图。用增广路算法求出最大匹配数。
二分图匹配,因为没有分左右每对匹配会出现两次。 最后算出来的 ans 要除以2;

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
using namespace std;
const int MaxN = 510, MaxM = 250010;;
int head[MaxN], ver[MaxM], Next[MaxM], match[MaxN];
int n, tot;
bool vis[MaxN];void add(int x, int y)
{
    ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}bool dfs(int x)
{
    for(int i = head[x]; i; i = Next[i]){
    int y = ver[i];if(!vis[y]){
    vis[y] = true;if(!match[y] || dfs(match[y])){
    match[y] = x;return true;}}}return false;
}int main()
{
    char s[10] = {
    0};int k;while(scanf("%d", &n) != EOF){
    int j;tot = 0;memset(head, 0, sizeof head);memset(Next, 0, sizeof Next);memset(match, 0, sizeof match);for(int i = 0; i < n; ++i){
    scanf("%s", s);	scanf("%s", s);	s[strlen(s) - 1] = '\0';k = atoi(s + 1);while(k--){
    scanf("%d", &j);		add(i, j);}}int ans = 0;for(int i = 0; i < n; ++i){
    memset(vis, 0, sizeof vis);if(dfs(i))++ans;}printf("%d\n", n - ans / 2);}return 0;
}/* 7 0: (3) 4 5 6 1: (2) 4 6 2: (0) 3: (0) 4: (2) 0 1 5: (1) 0 6: (2) 0 1 3 0: (2) 1 2 1: (1) 0 2: (1) 0 *//* 5 2 */
  相关解决方案