AOJ 1185: ACM洋菓子店

この記事もブログに記事を書きます 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);
	}
}