POJ 3020 Antenna Placement

問題

hxwのグリッドがあり、各マスはアンテナ'*'および何もない'o'のいずれかである。
縦または横に隣り合う二つ(一つだけでもかまわない)のアンテナを丸で囲む。
全てのアンテナを囲むのに必要な丸の数を求めよ。

制約条件

h≦40
w≦10

方針

アンテナを頂点とし、隣接関係があるアンテナ同士に辺を貼ったグラフを考えると、求めるのは最小辺カバーである。
アンテナのグラフは2部グラフ(x+yが奇数の頂点はx+yが偶数の頂点にしか接続しない)なので、最小辺カバーは最大マッチングを使えば解ける。

ソースコード

const int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
int h,w;
char in[40][11];
int k,num[400];

vector<vector<int> > G;

int p[500];
bool v[500];
bool match(int s){
  if(s<0)return 1;
  rep(i,G[s].size())if(!v[G[s][i]]){
    v[G[s][i]]=1;
    if(match(p[G[s][i]]))return p[G[s][i]]=s,p[s]=G[s][i], 1;
  }
  return 0;
}
int main(){
  int cs; scanf("%d",&cs);
  while(cs--){
    scanf("%d%d",&h,&w);
    rep(i,h)scanf("%s",in[i]);
    k=0;
    rep(i,h)rep(j,w)if(in[i][j]=='*')num[i*w+j]=k++;
    G.clear();
    G.resize(k);
    
    rep(i,h)rep(j,w)if(in[i][j]=='*'){
      rep(d,4){
        int y=i+dy[d],x=j+dx[d];
        if(0<=y&&y<h&&0<=x&&x<w&&in[y][x]=='*')G[num[i*w+j]].pb(num[y*w+x]);
      }
    }
    int ans=k;
    rep(i,k)p[i]=-1;
    rep(i,k)if(p[i]<0){
      rep(j,k)v[j]=0;
      if(match(i))ans--;
    }
    printf("%d\n",ans);
  }
  return 0;
}