POJ-3020: Antenna Placement

keyword

2部マッチング　C++

問題概要

H*W(H<40,W<10)のボードが与えられる。各セルはoか*で埋まっている。*を2*1の板で覆いたい(重なってもよいし、oの上に置いてもよい)。必要な板の最小枚数を求める問題。

解法

重なる部分を最小化すればよいことが分かる。ということで、隣接する*同士に辺をはった2部グラフの最大マッチング+マッチングで覆われていない頂点の個数が答えとなる。

感想

最近オンラインジャッジをだらだら解く悪癖がついてレーティング付きのコンテストに悪影響を及ぼしている気がするので実装の時間を計ることにした(アルゴリズムを考えて、頭の中で整理してから書き始めた時点がスタート)。早速2部グラフの最大マッチングを書き間違えてこんな簡単な問題に20分もかかってしまった。

#include <cstdio>
#include <vector>
#include <string.h>
using namespace std;

const int MAX_N = 40*10+9;

char board[50][20];
vector<int> G[MAX_N];
int H, W, N;
int dy[] = {0,0,1,-1};
int dx[] = {1,-1,0,0};
int match[MAX_N];
bool used[MAX_N];

void make_graph(){
    for(int i=0; i<H; i++)for(int j=0; j<W; j++)if(board[i][j]=='*')for(int k=0; k<4; k++){
        int ny = i + dy[k], nx = j + dx[k];
        if(0<=ny && ny<H && 0<=nx && nx<W && board[ny][nx]=='*'){
            G[i*W+j].push_back(ny*W+nx);
        }
    }
}

int solve(){
    make_graph();
    int ans = bipartite_matching();
    for(int i=0; i<H; i++)for(int j=0; j<W; j++)if(board[i][j] == '*' && match[i*W+j]==-1){
        ans++;
    }
    return ans;
}

int main(){
    int T;
    scanf("%d\n",&T);
    while(T--){
        scanf("%d%d ",&H,&W);
        N = H*W;
        for(int i=0; i<N; i++) G[i].clear();
        for(int i=0; i<H; i++){
            scanf("%s ",board[i]);
        }
        printf("%d\n",solve());
    }
    return 0;
}