この記事もブログに記事を書きます Advent Calendar 2014 - Adventarの記事です。
解説はHziwarAのask.fmもしくはtwilog参照。
ここまでad-hocらしいad-hocなフローは初めてみた。
ということで1000AC達成！
#include<stdio.h> #include<algorithm> #include<vector> #include<queue> using namespace std; const int D_MAX_V=21002; const int D_v_size=21002; struct D_wolf{ int t,c,r; D_wolf(){t=c=r=0;} D_wolf(int t1,int c1,int r1){ t=t1;c=c1;r=r1; } }; vector<D_wolf>D_G[D_MAX_V]; int D_level[D_MAX_V]; int D_iter[D_MAX_V]; void add_edge(int from,int to,int cap){ D_G[from].push_back(D_wolf(to,cap,D_G[to].size())); D_G[to].push_back(D_wolf(from,0,D_G[from].size()-1)); } void D_bfs(int s){ for(int i=0;i<D_v_size;i++)D_level[i]=-1; queue<int> Q; D_level[s]=0; Q.push(s); while(Q.size()){ int v=Q.front(); Q.pop(); for(int i=0;i<D_G[v].size();i++){ if(D_G[v][i].c>0&&D_level[D_G[v][i].t]<0){ D_level[D_G[v][i].t]=D_level[v]+1; Q.push(D_G[v][i].t); } } } } int D_dfs(int v,int t,int f){ if(v==t)return f; for(;D_iter[v]<D_G[v].size();D_iter[v]++){ int i=D_iter[v]; if(D_G[v][i].c>0&&D_level[v]<D_level[D_G[v][i].t]){ int d=D_dfs(D_G[v][i].t,t,min(f,D_G[v][i].c)); if(d>0){ D_G[v][i].c-=d; D_G[D_G[v][i].t][D_G[v][i].r].c+=d; return d; } } } return 0; } int max_flow(int s,int t){ int flow=0; for(;;){ D_bfs(s); if(D_level[t]<0)return flow; for(int i=0;i<D_v_size;i++)D_iter[i]=0; int f; while((f=D_dfs(s,t,99999999))>0){flow+=f;} } return 0; } char str[110][110]; int t[110][110]; int y[110][110]; int dt[11000]; int dy[11000]; int p[11000]; int q[11000]; int main(){ int a,b; while(scanf("%d%d",&a,&b),a){ for(int i=0;i<a;i++)scanf("%s",str[i]); int tn=0; int yn=0; for(int i=0;i<a-1;i++){ int last=0; for(int j=0;j<b;j++){ if(str[i][j]=='#'&&str[i+1][j]=='#'){ last=1; y[i][j]=yn; }else if(last){ yn++; last=0; } } if(last){ yn++; } } for(int i=0;i<b-1;i++){ int last=0; for(int j=0;j<a;j++){ if(str[j][i]=='#'&&str[j][i+1]=='#'){ last=1; t[j][i]=tn; }else if(last){ tn++; last=0; } } if(last)tn++; } for(int i=0;i<21002;i++){ D_G[i].clear(); D_level[i]=D_iter[i]=0; } for(int i=0;i<11000;i++)dt[i]=dy[i]=0; int sz=0; for(int i=0;i<a-1;i++)for(int j=0;j<b-1;j++){ if(str[i][j]=='#'&&str[i][j+1]=='#'&&str[i+1][j]=='#'&&str[i+1][j+1]=='.'){ p[sz]=t[i][j];q[sz++]=y[i][j]; dt[t[i][j]]++;dy[y[i][j]]++; } if(str[i][j]=='#'&&str[i][j+1]=='#'&&str[i+1][j]=='.'&&str[i+1][j+1]=='#'){ p[sz]=t[i][j];q[sz++]=y[i][j+1]; dt[t[i][j]]++;dy[y[i][j+1]]++; } if(str[i][j]=='#'&&str[i][j+1]=='.'&&str[i+1][j]=='#'&&str[i+1][j+1]=='#'){ p[sz]=t[i+1][j];q[sz++]=y[i][j]; dt[t[i+1][j]]++;dy[y[i][j]]++; } if(str[i][j]=='.'&&str[i][j+1]=='#'&&str[i+1][j]=='#'&&str[i+1][j+1]=='#'){ p[sz]=t[i+1][j];q[sz++]=y[i][j+1]; dt[t[i+1][j]]++;dy[y[i][j+1]]++; } } int S=tn+yn; int T=tn+yn+1; int n=0; for(int i=0;i<tn;i++)if(dt[i]>=2){add_edge(S,i,1);n++;} for(int i=0;i<yn;i++)if(dy[i]>=2){add_edge(i+tn,T,1);n++;} for(int i=0;i<sz;i++){ if(dt[p[i]]>=2&&dy[q[i]]>=2)add_edge(p[i],q[i]+tn,1); } for(int i=0;i<a-1;i++){ for(int j=0;j<b-1;j++){ if(str[i][j]=='#'&&str[i][j+1]=='#'&&str[i+1][j]=='#'&&str[i+1][j+1]=='#'){ int L=t[i][j]; int R=y[i][j]; if(dt[L]>=2&&dy[R]>=2)add_edge(L,R+tn,1); } } } int val=n-max_flow(S,T); printf("%d\n",sz-val+1); } }
