最大獨立集，把不認識的男女看成是有矛盾的，要選出一些互相沒有矛盾的男女。

View Code #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std;#define maxn 205bool g[maxn][maxn]; int uN, vN, m; int xM[maxn], yM[maxn]; bool chk[maxn];void input() {for (int i = 0; i < m; i++){int a, b;scanf("%d%d", &a, &b);g[--a][--b] = true;}for (int i = 0; i < uN; i++)for (int j = 0; j < vN; j++)g[i][j] = !g[i][j]; }bool SearchPath(int u) {int v;for (v = 0; v < vN; v++)if (g[u][v] && !chk[v]){chk[v] = true;if (yM[v] == -1 || SearchPath(yM[v])){yM[v] = u;xM[u] = v;return true;}}return false; }int MaxMatch() {int u, ret = 0;memset(xM, -1, sizeof(xM));memset(yM, -1, sizeof(yM));for (u = 0; u < uN; u++){if (xM[u] == -1){memset(chk, false, sizeof(chk));if (SearchPath(u))ret++;}}return ret; }int main() {//freopen("t.txt", "r", stdin);int t = 0;while (scanf("%d%d%d", &uN, &vN, &m), uN | vN | m){t++;memset(g, 0, sizeof(g));input();printf("Case %d: %d\n", t, uN + vN - MaxMatch());}return 0; }

轉載于:https://www.cnblogs.com/rainydays/archive/2012/07/06/2578868.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的poj3692的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。