POJ 2226 Muddy Fields（最小点覆盖）题解

题意：一片r*c的地，有些地方是泥地，需要铺地板。这些地板宽1，长无限，但只能铺在泥地上不能压到其他地方，问你铺满所有泥地最少几块

思路：我们把一行中连续的泥地看成整体，并把所有横的整体里的点编成一个id号，同样把竖的所有整体编号，这样一个点就有横竖两个编号，那么我给这两个编号连边，那么只要涂这个边就代表了这个点被模板盖住了，那么问题就转化为了最小点覆盖

思路：poj2226-Muddy Fields

代码：

#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
const int maxn = 1250 + 10;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int linker[maxn];
bool used[maxn];
struct node{
    int row, col;
}p[maxn][maxn];
int n;
int head[maxn], tot;
struct Edge{
    int to, next;
}edge[maxn * maxn];
char mp[maxn][maxn];
void init(){
    memset(head, -1, sizeof(head));
    tot = 0;
}
void addEdge(int u, int v){
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
bool dfs(int u){
    for(int i = head[u]; i != -1; i = edge[i].next){
        int v = edge[i].to;
        if(!used[v]){
            used[v] = true;
            if(linker[v] == -1 || dfs(linker[v])){
                linker[v] = u;
                return true;
            }
        }
    }
    return false;
}
int hungry(){
    int res = 0;
    memset(linker, -1, sizeof(linker));
    for(int u = 1; u <= n; u++){
        memset(used, false, sizeof(used));
        if(dfs(u)) res++;
    }
    return res;
}
int main(){
    int r, c;
    while(~scanf("%d%d", &r, &c)){
        n = 0;
        init();
        for(int i = 1; i <= r; i++){
            scanf("%s", mp[i] + 1);
            for(int j = 1; j <= c; j++){
                p[i][j].col = p[i][j].row = 0;
            }
        }
        for(int i = 1; i <= r; i++){
            for(int j = 1; j <= c; j++){
                if(mp[i][j] == '*'){
                    if(j > 1 && mp[i][j - 1] == '*'){
                        p[i][j].row = p[i][j - 1].row;
                    }
                    else{
                        p[i][j].row = ++n;
                    }
                }
            }
        }
        for(int i = 1; i <= r; i++){
            for(int j = 1; j <= c; j++){
                if(mp[i][j] == '*'){
                    if(i > 1 && mp[i - 1][j] == '*'){
                        p[i][j].col = p[i - 1][j].col;
                    }
                    else{
                        p[i][j].col = ++n;
                    }
                    addEdge(p[i][j].row, p[i][j].col);
                }
            }
        }
        printf("%d
", hungry());
    }
    return 0;
}