題意：一片r*c的地，有些地方是泥地，需要鋪地板。這些地板寬1，長無限，但只能鋪在泥地上不能壓到其他地方，問你鋪滿所有泥地最少幾塊
python局部高點算法，思路：我們把一行中連續的泥地看成整體，并把所有橫的整體里的點編成一個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\n", hungry());}return 0; }
?
