KUPC2016 : E - 柵 / Fences

これも発想勝負かも。
http://kupc2016.contest.atcoder.jp/tasks/kupc2016_e

問題

グリッドのうち一部のセルにヤギがいる。
一部のセルを移動不可とし、ヤギが隣接マスを辿って縁のマスに到達できないようにしたい。
最低何セルを移動不可にすればよいか。

解法

最大フロー最小カット定理で解く。
各セルを2つの頂点とし、隣接マスへ出ていくための点と、隣接マスから入ってくる点に分ける。
隣接マス間や、上記2頂点間を無限大の容量の辺でつなぎ、ヤギのセルから縁のセルへの最大フロー＝最小カットを求めよう。

int H,W;
string S[202];

template<class V> class MaxFlow_Ford {
public:
	struct edge { int to,reve;V cap;};
	static const int MV = 30000;
	vector<edge> E[MV];
	int vis[MV];
	void add_edge(int x,int y,V cap,bool undir=false) {
		E[x].push_back((edge){y,(int)E[y].size(),cap});
		E[y].push_back((edge){x,(int)E[x].size()-1,undir?cap:0});
	}
	V dfs(int from,int to,V cf) {
		V tf;
		if(from==to) return cf;
		vis[from]=1;
		FORR(e,E[from]) if(vis[e.to]==0 && e.cap>0 && (tf = dfs(e.to,to,min(cf,e.cap)))>0) {
			e.cap -= tf;
			E[e.to][e.reve].cap += tf;
			return tf;
		}
		return 0;
	}
	V maxflow(int from, int to) {
		V fl=0,tf;
		while(1) {
			ZERO(vis);
			if((tf = dfs(from,to,numeric_limits<V>::max()))==0) return fl;
			fl+=tf;
		}
	}
};

MaxFlow_Ford<int> mf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	FOR(y,H) if(S[y][0]=='X' || S[y][W-1]=='X') return _P("-1\n");
	FOR(x,W) if(S[0][x]=='X' || S[H-1][x]=='X') return _P("-1\n");
	
	FOR(y,H) FOR(x,W) {
		mf.add_edge(y*100+x,10000+y*100+x,(S[y][x]=='X')?101010:1);
		if(S[y][x]=='X') mf.add_edge(20010,y*100+x,101010);
		if(y==0 || x==0 || y==H-1 || x==W-1) mf.add_edge(10000+y*100+x,20011,101010);
		if(y) mf.add_edge(10000+y*100+x,(y-1)*100+x,101010);
		if(x) mf.add_edge(10000+y*100+x,y*100+(x-1),101010);
		if(y<H-1) mf.add_edge(10000+y*100+x,(y+1)*100+x,101010);
		if(x<W-1) mf.add_edge(10000+y*100+x,y*100+(x+1),101010);
	}
	cout<<mf.maxflow(20010,20011)<<endl;
	
}

まとめ

最初Union-Findとかこねくり回してだいぶ手間取った。