本文主要是介绍POJ 2226 二分图 最小点覆盖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这题的建图比较神
首先要明白题意是要覆盖所有的污泥，而不能把草地也给覆盖了
刚开始我就把草地也给覆盖了，显然不行。
那么就需要划分为一个一个的线段来进行覆盖
将所有横着的线段分别预处理出来，每个线段给一个编号
同样所有竖着的线段预处理出来。注意只要是连续的几个污泥块就属于同一个线段，横着的和竖着的分别处理。
然后对每个污泥，用其所属的横线段的编号跟所属的竖线段的编号连边。
最后转化为最小点覆盖模型。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 1111
#define MAXM 320005
#define INF 100000007
using namespace std;
int r, c;
char s[MAXN][MAXN];
struct EDGE
{int v, next;
}edge[MAXM];
int head[MAXN], e;
int vis[MAXN], link[MAXN];
int he, sh;
int ida[MAXN][MAXN], idb[MAXN][MAXN];
void init()
{memset(head, -1, sizeof(head));e = 0;
}
void add(int x, int y)
{edge[e].v = y;edge[e].next = head[x];head[x] = e++;
}
void get()
{for(int i = 0; i < r; i++) scanf("%s", s[i]);he = sh = 0;for(int i = 0; i < r; i++)for(int j = 0; j < c; j++)if(s[i][j] == '*'){if(j && s[i][j - 1] == '*') ida[i][j] = ida[i][j - 1];else ida[i][j] = ++he;}for(int i = 0; i < c; i++)for(int j = 0; j < r; j++)if(s[j][i] == '*'){if(j && s[j - 1][i] == '*') idb[j][i] = idb[j - 1][i];else idb[j][i] = ++sh;}for(int i = 0; i < r; i++)for(int j = 0; j < c; j++)if(s[i][j] == '*')add(ida[i][j], idb[i][j]);
}
int dfs(int u)
{for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].v;if(!vis[v]){vis[v] = 1;if(link[v] == -1 || dfs(link[v])){link[v] = u;return 1;}}}return 0;
}
int solve()
{int ans = 0;memset(link, -1, sizeof(link));for(int i = 1; i <= he; i++){memset(vis, 0, sizeof(vis));ans += dfs(i);}return ans;
}
int main()
{init();scanf("%d%d", &r, &c);get();printf("%d\n", solve());return 0;
}
这篇关于POJ 2226 二分图 最小点覆盖的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
