PKU-2226: Muddy Fields

keyword

2部グラフ　最小点被覆　C++

問題概要

W*H(W,H<50)のボードがあり、各マスは空か泥が入っている。幅1、長さ任意の板があり、板を使って泥のあるマスを埋めたい。泥のないマスには板を乗せてはならない。使う板の最小枚数を求める問題。

解法

板を置くのは連続した部分の左端か上端になる。全ての泥があるマスに対して、連続した左端のノード(in A)と上端のノード(in B)を繋いで2部グラフを作る(A群とB群は別)。あとは最小点被覆なので、例によって最大マッチングを求める。

int solve(){
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++)if(board[i][j]=='*'){
            int p = i, q = j;
            while(p>0 && board[p-1][j]=='*')p--;
            while(q>0 && board[i][q-1]=='*')q--;
            add_edge(p*50+j, i*50+q+2500);
        }
    }
    return bipartite_matching();
}