无向图的最大独立集。
二部图中:
最大独立集 = 顶点数-最小点覆盖集
最小点覆盖集 = 最大匹配
#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 void read_graph(int u, int v) { edge[cnt].v = v; edge[cnt].next = first[u], first[u] = cnt++; } bool ED(int u) { for(int e = first[u]; e != -1; e = edge[e].next) { int v = edge[e].v; if(!vis[v]) { vis[v] = 1; if(link[v] == -1 || ED(link[v])) { link[v] = u; return true; } } } return false; } void solve() { int ans = 0; for(int i = 0; i < nx; i++) //从0开始的 { memset(vis, 0, sizeof(vis)); if(ED(i)) ans++; } printf("%d\n", nx-ans/2); //估计是无向图,重复了 } void read_case() { init(); ny = nx; for(int u = 0; u < nx; u++) { int p, m; scanf("%d: (%d)", &p, &m); for(int i = 1; i <= m; i++) { int v; scanf("%d", &v); read_graph(u, v); } } } int main() { while(~scanf("%d", &nx)) { read_case(); solve(); } return 0; }