SRM 625

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;
	}
};

External link:

https://gist.github.com/lychees/3829f110b3f9317800ac