这题的建图比较神
首先要明白题意是要覆盖所有的污泥,而不能把草地也给覆盖了
刚开始我就把草地也给覆盖了,显然不行。
那么就需要划分为一个一个的线段来进行覆盖
将所有横着的线段分别预处理出来,每个线段给一个编号
同样所有竖着的线段预处理出来。注意只要是连续的几个污泥块就属于同一个线段,横着的和竖着的分别处理。
然后对每个污泥,用其所属的横线段的编号跟所属的竖线段的编号连边。
最后转化为最小点覆盖模型。
#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初级-图算法 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ 最接近点对问题 ACM北大 using namespace std; struct Point { float x; float y; };
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ2009年最新版,相当详细.................
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ2002-Squares 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ1048,加强版的约瑟夫问题 难度中等