挑战程序设计竞赛，283页，二分图最大团
题目意思：
幼儿园，所有女生相互之间认识，所有男生之间相互认识，有些女生和某些男生认识。
现在，老师想挑选一些孩子玩游戏，这需要所有玩家彼此认识。您将帮助查找老师可以挑选的最大孩子数。
本题要点：
1、二分图的团：
二分图的子图中，左部的任意一个节点和右部所有的节点都有连线，该子图称为二分图的 团。
点数最多的团，称为二分图的最大团。
2、二分图G 的补图 G1, G的最大团等于其补图G1的最大独立集。
3、二分图的最大独立集 = 二分图的总点数 - 二分图的最大匹配数
绕到最后，还是用 增广路算法，求二分图的最大匹配数.
我要评论#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 210;
int a[MaxN][MaxN], match[MaxN];
bool vis[MaxN];
int g, b, m;
int complementary[MaxN][MaxN]; //补图
bool dfs(int x)
{
for(int y = 1; y <= b; ++y)
{
if(!complementary[x][y] || vis[y])
continue;
vis[y] = true;
if(!match[y] || dfs(match[y]))
{
match[y] = x;
return true;
}
}
return false;
}
int main()
{
int cnt = 0, x, y;
while(scanf("%d%d%d", &g, &b, &m) != EOF)
{
if(0 == g && 0 == b && 0 == m)
break;
memset(a, 0, sizeof a);
memset(match, 0, sizeof match);
memset(complementary, 0, sizeof complementary);
while(m--)
{
scanf("%d%d", &x, &y);
a[x][y] = 1;
}
for(int i = 1; i <= g; ++i)
{
for(int j = 1; j <= b; ++j)
{
if(!a[i][j])
{
complementary[i][j] = 1;
}
}
}
int ans = 0;
for(int i = 1; i <= g; ++i)
{
memset(vis, 0, sizeof vis);
if(dfs(i))
++ans;
}
printf("Case %d: %d\n", ++cnt, g + b - ans);
}
return 0;
}
/*
2 3 3
1 1
1 2
2 3
2 3 5
1 1
1 2
2 1
2 2
2 3
0 0 0
*/
/*
Case 1: 3
Case 2: 4
*/
本文地址：https://blog.csdn.net/qq_38232157/article/details/107337801
如对本文有疑问， 点击进行留言回复！！
web前端基础之HTML5语义化新标签学习笔记（8）学会用语义化标签
网友评论