本文主要是介绍poj 2594 二分图最大独立集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
求一张图的最大独立集，这题不同的地方在于，间接相邻的点也可以有一条边，所以用floyd来把间接相邻的边也连起来。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <climits>
#include <cassert>
#define LL long longusing namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1000 + 10;
const double eps = 1e-8;
const double pi = acos(-1.0);
const double ee = exp(1.0);int dir[][2] = { {0, 1}, {1, 0}, {-1, 0}, {0, -1} };int mp[maxn][maxn];
vector<int> g[maxn];
int fr[maxn];
bool vis[maxn];
int n, m;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;memset(fr, -1, sizeof(fr));for (int i = 0; i < n; i++){memset(vis, false, sizeof(vis));if (match(i)){ret++;}}return ret;
}void floyd()
{for (int k = 0; k < n; k++){for (int i = 0; i < n; i++){for(int j = 0; j < n; j++){if (mp[i][k] && mp[k][j]){mp[i][j] = 1;g[i].push_back(j);}}}}
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCAlwhile (~scanf("%d%d", &n, &m)){if (!n && !m)break;for (int i = 0; i <= n; i++){g[i].clear();}memset(mp, 0, sizeof(mp));while (m--){int fr, to;scanf("%d%d", &fr, &to);fr--,to--;g[fr].push_back(to);mp[fr][to] = 1;}floyd();printf("%d\n", n - hungary());}return 0;
}
这篇关于poj 2594 二分图最大独立集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
