ありよりのあり

\主に競プロ備忘録/

CODE THANKS FESTIVAL 2017 G - Mixture Drug

問題概要

N辺M頂点のグラフが与えられる.
頂点集合S⊆VでSに含まれる二頂点を結ぶ辺が存在しないようなSのmax(|S|)を求めよ.
1 <= N <= 40

解法

解説がめっちゃ丁寧.

半分全列挙して4回ぐらいbitDPする.
Vに含まれる二頂点に含まれる辺が存在しないという条件をVが独立であるという.
V = V1 ∪ V2 , V1 ∩ V2 = φ, |V1| = N/2 として,
ok1[v1] := (v1⊆V1は独立であるか)
ok2[v2] := (v2⊆V2は独立であるか)
ok3[v1] := (v1⊆V1と連結でないv2⊆V2全体の集合)
dp[v1] := (独立なv2⊆ok3[v1]の最大|v2|)
ここで,ok3[v1]自体は独立でないことに注意する.

以上をbitDPを用いて出すと,各v1⊆V1について
max(|v1| + dp[v1])が答えとなる.

メモ

これ最小カットでいけるんじゃと思ったけど同じ側にあるとペナルティはうまくいかないみたいだった.
DPの遷移が理解するのに時間かかった.
普通にfor文を回したらS -> S∪a -> S∪a∪b と遷移できることがイメージできてなかった気がする.
dp[S∪a]->dp[S∪a∪b], dp[S∪b]->dp[S∪a∪b] の前に dp[S] -> dp[S∪a] と dp[S] -> dp[S∪b] が来ないとおかしくなるじゃんと思ったけど冷静に見ると絶対にそうなっている.
結構好きな問題なのでそのうちまた解きたい.
追記:
最大独立集合問題 <-> 補グラフに関する最大クリーク

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 41;

vector<int> graph[40];
bool ok1[1<<20],ok2[1<<20];
int ok3[1<<20],dp[1<<20];

int main() {
  int N,M; cin >> N >> M;
  rep(i,M){
    int a,b; cin >> a >> b;
    a--; b--; graph[a].pb(b); graph[b].pb(a);
  }
  int n1 = (N+1)/2; int n2 = N/2;
  fill(ok1,ok1+(1<<n1),true);
  rep(i,n1) for(auto u:graph[i]) if(u<n1) ok1[(1<<i)|(1<<u)] = false;
  rep(i,1<<n1) if(!ok1[i]) rep(j,n1) ok1[i|(1<<j)] = false;
  
  fill(ok2,ok2+(1<<n2),true);
  REP(i,n1,N) for(auto u:graph[i]) if(u>=n1) ok2[(1<<(i-n1))|(1<<(u-n1))] = false;
  rep(i,1<<n2) if(!ok2[i]) rep(j,n2) ok2[i|(1<<j)] = false;

  ok3[0] = (1<<n2) - 1;
  rep(i,n1){
    ok3[1<<i] = (1<<n2) - 1;
    for(auto u:graph[i]) if(u>=n1) ok3[1<<i] ^= (1<<(u-n1));
  }
  rep(i,1<<n1) rep(j,n1) ok3[i|(1<<j)] = ok3[i]&ok3[1<<j];

  rep(i,1<<n2){
    if(ok2[i]){
      int cnt = 0;
      rep(j,n2) if(i&(1<<j)) cnt++;
      dp[i] = cnt;
    }else{
      dp[i] = 0;
    }
  }
  rep(i,1<<n2) rep(j,n2) dp[i|(1<<j)] = max(dp[i|(1<<j)],dp[i]);

  int ans = 0;
  rep(i,1<<n1){
    if(!ok1[i]) continue;
    int cnt = 0;
    rep(j,n1) if(i&(1<<j)) cnt++;
    ans = max(ans,cnt + dp[ok3[i]]);
  }
  cout << ans << endl;
  return 0;
}