AtCoder Regular Contest 074: Lotus Leaves

http://arc074.contest.atcoder.jp/tasks/arc074_d

flow。

行と列を代表する頂点を用意してうまく辺を張ると、辺の本数がO(H*W)になって十分高速。

int H, W;
string S[MAX_N];


void solve() {
	cin >> H >> W;
	int s, t;
	rep(i, 0, H) {
		cin >> S[i];
		rep(j, 0, W) {
			int id = i * W + j;
			if(S[i][j] == 'S') {
				s = id * 2 + 1;
			}
			if(S[i][j] == 'T') {
				t = id * 2;
			}
			if(S[i][j] != '.') {
				add_edge(id * 2, id * 2 + 1, 1);
				add_edge(id * 2 + 1, H * W * 2 + j, inf);
				add_edge(H * W * 2 + j, id * 2, inf);
				add_edge(id * 2 + 1, H * W * 2 + i + W, inf);
				add_edge(H * W * 2 + i + W, id * 2, inf);
			}
		}
	}
	int res = max_flow(s, t);
	if(res >= inf) cout << "-1\n"; 
	else cout << res << "\n";
}

フローの計算量の見積もり方がよくわからない…