## 500. BlockTheBlockPuzzle

### Brief description:

… 略）

### Analysis:

比較裸的最小割，注意拆點。

int minimumHoles(vector <string> board) { r = board.size (), c = board[0].size (); init(); REP_2(i, j, r, c) if (board[i][j] == 'b'){ add_edge(s, V(i, j, 1), INF); add_edge(V(i, j), V(i, j, 1), INF); } else if (board[i][j] == '$'){ t = V(i, j, 1); add_edge(V(i, j), V(i, j, 1), INF); board[i][j] = 'b'; } else if (board[i][j] == '.'){ add_edge(V(i, j), V(i, j, 1), 1); } REP_2(i, j, r, c){ if (j+3 < c){ int cc = (board[i][j+1] == 'b') || (board[i][j+2] == 'b') ? INF : (board[i][j+1] == '.') + (board[i][j+2] == '.'); add_edge(V(i, j, 1), V(i, j+3), cc); add_edge(V(i, j+3, 1), V(i, j), cc); } if (i+3 < r){ int cc = (board[i+1][j] == 'b') || (board[i+2][j] == 'b') ? INF : (board[i+1][j] == '.') + (board[i+2][j] == '.'); add_edge(V(i, j, 1), V(i+3, j), cc); add_edge(V(i+3, j, 1), V(i, j), cc); } } return Dinitz(); }

## 900. Seatfriends

### Brief description:

略。）

### Analysis:

。。。dp[i][j] 表示 i 個人、 j 個 cluster 時的方案數。。。

。。主要就是搞兩次。dp 時。不要去處理 `cluster`

間具體有多少空格的問題。。

。再往之間插入空格就行了。。。

const int N = 2009; Int dp[2][N], Binom[N][N]; class Seatfriends { public: int countseatnumb(int n, int m, int g) { REP(i, N){Binom[i][0] = 1; REP_1(j, i) Binom[i][j] = Binom[i-1][j-1] + Binom[i-1][j];} #define u dp[q][j] #define v dp[p] int p = 0, q = 1; RST(dp[p]); dp[p][1] = n; FOR(i, 1, m){ swap(p, q); RST(dp[p]); REP_1(j, g) if (u){ v[j] += u*j*2; v[j+1] += u*j; v[j-1] += u*j; } } if (n == m) return dp[p][0]; Int res = 0; REP_1(i, g) res += dp[p][i] * Binom[n-m-1][i-1]; return res; } };