无向图的最大独立集。
二部图中:
最大独立集 = 顶点数-最小点覆盖集
最小点覆盖集 = 最大匹配
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 510;
const int MAXM = 40010;
struct Edge
{
int v, next;
}edge[MAXM];
int first[MAXN], link[MAXN];
bool vis[MAXN];
int nx, ny;
int cnt;
inline void init()
{
cnt = 0;
memset(first, -1, sizeof(first));
memset(link, -1, sizeof(link));
}
inline voi......
阅读全文