POJ 2226 Muddy Fields (最小点覆盖集，对比POJ 3041)

题意

给出的是N*M的矩阵，同样是有障碍的格子，要求每次只能消除一行或一列中连续的格子，最少消除多少次可以全部清除。

思路

相当于POJ 3041升级版，不同之处在于这次不能一列一行全部消掉，那些非障碍的格子不能消。 但是我们还是要抓住关键点：每个格子必须消除，要么以行消，要么以列消。并且我们发现如果以行消得话，一定是以这连续障碍行的最左端为起点，同理列是以最上端为起点。那么我们就又把消除方式变成两种了。这时就可以把障碍当作边，两种覆盖方式分别作为两断点，求二分图最小点覆盖集。 行列方式的起点共有R*C种，即二分图两个点集均需要R*C个点。并且注意这题RC好像不止50= =……我的二分图点大小开到2000才从RE变成AC……

代码

 

using namespace std;
const int MAXV = 2005;                   //N1+N2
vector  adj[MAXV];
struct MaximumMatchingOfBipartiteGraph{
    int vn;
    void init(int n){                   //二分图两点集点的个数
        vn = n;
        for (int i = 0; i <= vn; i ++)     adj[i].clear();
    }
    void add_uedge(int u, int v){
		adj[u].push_back(v);
		adj[v].push_back(u);
    }
    bool vis[MAXV];
    int mat[MAXV];                      //记录已匹配点的对应点
    bool cross_path(int u){
        for (int i = 0; i < (int)adj[u].size(); i ++){
            int v = adj[u][i];
            if (!vis[v]){
                vis[v] = true;
                if (mat[v] == 0 || cross_path(mat[v])){
                    mat[v] = u;
                    mat[u] = v;
                    return true;
                }
            }
        }
        return false;
    }
    int hungary(){
        mem(mat, 0);
        int match_num = 0;
        for (int i = 1; i <= vn; i ++){
            mem(vis, 0);
            if (!mat[i] && cross_path(i)){
                match_num ++;
            }
        }
        return match_num;
    }
    void print_edge(){
        for (int i = 1; i <= vn; i ++){
            for (int j = 0; j < (int)adj[i].size(); j ++){
                printf("u = %d v = %d
", i, adj[i][j]);
            }
        }
    }
}match;

char map[MAXV][MAXV];
int main(){
	//freopen("test.in", "r", stdin);
	//freopen("test.out", "w", stdout);
    int r, c;
    scanf("%d %d", &r, &c);
    getchar();
    match.init(r*c*2);
    for (int i = 0; i < r; i ++){
        for (int j = 0; j < c; j ++){
            scanf("%c", &map[i][j]);
            if (map[i][j] == '*'){
                int k = j - 1, l = i -1;
                while(k >= 0 && map[i][k] == '*'){
                    k --;
                }
                k ++;
                while(l >= 0 && map[l][j] == '*'){
                    l --;
                }
                l ++;
                match.add_uedge(i*c+k+1, r*c+l*c+j+1);
            }
        }
        getchar();
    }
    //match.print_edge();
    printf("%d
", match.hungary());
	return 0;
}