最大安定集合 (自分用) ～C - 広告～

最大安定集合（最大独立集合）とは

• グラフにて、辺でつながった２頂点の両方は選べないとしたときに選べる頂点の最大数
• 具体例「嫌いを辺で表した時に、何人スタッフを選べるか」

2部グラフなら最大マッチングで解ける

• Quiz
  • C - 広告 https://atcoder.jp/contests/soundhound2018/tasks/soundhound2018_c
• AC https://atcoder.jp/contests/soundhound2018/submissions/19219784
• ステップ
  • 最大安定集合を求めればいい
  • グリッドグラフは2部グラフ
  • 最大マッチングが求まればいい→フロー→（今回はACLを使用）

注意点

• 適当に両方向に辺を張ったらWAした。両方向に張ると下図のように水が縦横無尽に流れそうで怪しい
• 一方向に流れるようにするのが安全

#include <atcoder/maxflow>
using namespace atcoder; // 忘れがち

int dx[4] = {-1, 0, 1,  0};
int dy[4] = { 0, 1, 0, -1};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll H,W;
    cin>>H>>W;

    VS S(H);
    rep(i,H)cin>>S[i];

    ll N = H*W;

    mf_graph<ll> g(N+2);
    ll start=N;
    ll end=N+1;

    auto in_range = [&](ll i, ll j){
      if(0<=i && i<H && 0<=j && j<W){
        return true;
      }else{
        return false;
      }
    };

    auto get_id = [&](ll y, ll x){
      return W*y + x;
    };

    // start -> black -> white -> end
    // black : id=0 (mod 2)
    // white : id=1 (mod 2)
    ll vertex_cnt=0;
    rep(i,H){
      rep(j,W){
        if(S[i][j]=='*')continue;
        vertex_cnt++;
        ll now = get_id(i,j);

        // super 
        if((i+j)%2==0){
          g.add_edge(start,now,1);
        }
        else{
          g.add_edge(now,end,1);  
        }
        
        if((i+j)%2==1)continue;
        // 4方向。black->whiteの方向しか流さないこと
        rep(k,4){
          ll ny = i+dy[k];
          ll nx = j+dx[k];
          if(in_range(ny,nx)){
            g.add_edge(now, get_id(ny,nx), 1);
          }
        }
      }
    }
    ll match = g.flow(start,end); // 約O(NM)
    ll max_stable_set = vertex_cnt - match; // 最大安定集合
    p(max_stable_set);

    return 0;
}