本文主要是介绍poj 3692 二分图最大独立集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
幼儿园里，有G个女生和B个男生。
他们中间有女生和女生认识，男生男生认识，也有男生和女生认识的。
现在要选出一些人，使得这里面的人都认识，问最多能选多少人。
解析：
反过来建边，将不认识的男生和女生相连，然后求一个二分图的最大独立集就行了。
下图很直观：
点击打开链接
原图：
现图：
、
代码：
#pragma comment(linker, "/STACK:1677721600")
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include <algorithm>
#define pb push_back
#define mp make_pair
#define LL long long
#define lson lo,mi,rt<<1
#define rson mi+1,hi,rt<<1|1
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a,b) memset(a,b,sizeof(a))
#define FIN freopen("in.txt", "r", stdin)
#define FOUT freopen("out.txt", "w", stdout)using namespace std;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double ee = exp(1.0);
const int inf = 0x3f3f3f3f;
const int maxn = 500 + 10;
const double pi = acos(-1.0);
const LL iinf = 0x3f3f3f3f3f3f3f3f;vector<int> g[maxn];
int fr[maxn];
bool vis[maxn];
int V;bool match(int v)
{for (int i = 0; i < g[v].size(); i++){int u = g[v][i];if (!vis[u]){vis[u] = true;if (fr[u] == -1 || match(fr[u])){fr[u] = v;return true;}}}return false;
}int hungary()
{int ret = 0;mem1(fr);for (int i = 0; i < V; i++){mem0(vis);if (match(i)){ret++;}}return ret;
}bool matrix[maxn][maxn];int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCAlint G, B, M;int ca = 1;while (~scanf("%d%d%d", &G, &B, &M) && G){V = G + B;mem0(matrix);for (int i = 0; i < V; i++){g[i].clear();}for (int i = 0; i < M; i++){int fr, to;scanf("%d%d", &fr, &to);fr--, to--;matrix[fr][to] = true;}for (int i = 0; i < G; i++){for (int j = 0; j < B; j++){if (!matrix[i][j]){g[i].pb(j + G);g[j + G].pb(i);}}}printf("Case %d: %d\n", ca++, V - hungary() / 2);}return 0;
}
这篇关于poj 3692 二分图最大独立集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
