This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// 無向非連結グラフの最大独立集合 (maximal independent set) // 頂点の集合 V であって、V の任意の 2 つをつなぐ辺が存在しない場合 // 次数 1 であれば必ず採用・そうでなければ次数が大きいものから試す、 // とすると枝刈りがきいて高速になる const int GRAPH_SIZE = 40; using gbit = bitset<GRAPH_SIZE>; // bitset には比較演算子がないので・・・ namespace std { bool operator<(const gbit &a, const gbit &b) { gbit ab = a ^ b; int k = ab._Find_first(); return k < GRAPH_SIZE and b[k] == 1; } } template <typename CostType = int> struct MaximalIndependentSet { Graph<int> G; int N; vector<CostType> costs; gbit alive; vector<gbit> adj; bool weighted; map<gbit, CostType> rec; // 無向グラフを入力として与える MaximalIndependentSet(Graph<int> G_, vector<CostType> costs_ = vector<CostType>()) : G(G_), costs(costs_) { N = G_.size(); if(costs.size() != N) { costs = vector<CostType>(N, 1); weighted = false; } else weighted = true; alive = gbit(); adj = vector<gbit>(N); for(int i=0; i<N; i++) { alive[i] = true; for(auto e : G[i]) adj[i][e.to] = 1; } } inline int deg(int v) { return (alive & adj[v]).count(); } // その時点で次数最大の頂点を見つける int argmax_deg() { int max_deg = -1, res = -1; for(int i=0; i<N; i++) { if(!alive[i]) continue; int d = deg(i); if(d > max_deg) max_deg = d, res = i; } return res; } pair< CostType, gbit > solve_part1() { CostType d = 0; gbit res; // 次数 0 または 1 の頂点を全部見つける // 重みがある場合は 0 のみ for(int i=0; i<N; i++) { if(alive[i] and !res[i] and deg(i) <= !weighted) { res[i] = true; d += costs[i]; res |= (alive & adj[i]); } } return make_pair(d, res); } CostType solve_part2() { int v = argmax_deg(); CostType res = 0; if(v < 0) return CostType(0); // v を使わない alive[v] = false; res = max(res, solve()); // v を使う gbit vs = alive & adj[v]; alive ^= vs; res = max(res, solve() + costs[v]); alive ^= vs; alive[v] = true; return res; } CostType solve() { if(rec.count(alive)) return rec[alive]; CostType v1; gbit vs; tie(v1, vs) = solve_part1(); alive ^= vs; CostType v2 = solve_part2(); alive ^= vs; return rec[alive] = v1 + v2; } };
#line 1 "graph/graph_022_max_independent_set.cpp" // 無向非連結グラフの最大独立集合 (maximal independent set) // 頂点の集合 V であって、V の任意の 2 つをつなぐ辺が存在しない場合 // 次数 1 であれば必ず採用・そうでなければ次数が大きいものから試す、 // とすると枝刈りがきいて高速になる const int GRAPH_SIZE = 40; using gbit = bitset<GRAPH_SIZE>; // bitset には比較演算子がないので・・・ namespace std { bool operator<(const gbit &a, const gbit &b) { gbit ab = a ^ b; int k = ab._Find_first(); return k < GRAPH_SIZE and b[k] == 1; } } template <typename CostType = int> struct MaximalIndependentSet { Graph<int> G; int N; vector<CostType> costs; gbit alive; vector<gbit> adj; bool weighted; map<gbit, CostType> rec; // 無向グラフを入力として与える MaximalIndependentSet(Graph<int> G_, vector<CostType> costs_ = vector<CostType>()) : G(G_), costs(costs_) { N = G_.size(); if(costs.size() != N) { costs = vector<CostType>(N, 1); weighted = false; } else weighted = true; alive = gbit(); adj = vector<gbit>(N); for(int i=0; i<N; i++) { alive[i] = true; for(auto e : G[i]) adj[i][e.to] = 1; } } inline int deg(int v) { return (alive & adj[v]).count(); } // その時点で次数最大の頂点を見つける int argmax_deg() { int max_deg = -1, res = -1; for(int i=0; i<N; i++) { if(!alive[i]) continue; int d = deg(i); if(d > max_deg) max_deg = d, res = i; } return res; } pair< CostType, gbit > solve_part1() { CostType d = 0; gbit res; // 次数 0 または 1 の頂点を全部見つける // 重みがある場合は 0 のみ for(int i=0; i<N; i++) { if(alive[i] and !res[i] and deg(i) <= !weighted) { res[i] = true; d += costs[i]; res |= (alive & adj[i]); } } return make_pair(d, res); } CostType solve_part2() { int v = argmax_deg(); CostType res = 0; if(v < 0) return CostType(0); // v を使わない alive[v] = false; res = max(res, solve()); // v を使う gbit vs = alive & adj[v]; alive ^= vs; res = max(res, solve() + costs[v]); alive ^= vs; alive[v] = true; return res; } CostType solve() { if(rec.count(alive)) return rec[alive]; CostType v1; gbit vs; tie(v1, vs) = solve_part1(); alive ^= vs; CostType v2 = solve_part2(); alive ^= vs; return rec[alive] = v1 + v2; } };