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; }