POJ2226(最小顶点覆盖)
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 10044 | Accepted: 3743 |
Description
To prevent those muddy hooves, Farmer John will place a number of wooden boards over the muddy parts of the cows' field. Each of the boards is 1 unit wide, and can be any length long. Each board must be aligned parallel to one of the sides of the field.
Farmer John wishes to minimize the number of boards needed to cover the muddy spots, some of which might require more than one board to cover. The boards may not cover any grass and deprive the cows of grazing area but they can overlap each other.
Compute the minimum number of boards FJ requires to cover all the mud in the field.
Input
* Lines 2..R+1: Each line contains a string of C characters, with '*' representing a muddy patch, and '.' representing a grassy patch. No spaces are present.
Output
Sample Input
4 4
*.*.
.***
***.
..*.
Sample Output
4
思路:建图,求出横着的board与竖着的board。若两个board相交则建边,那么边其实为'*'。二分图的最小顶点覆盖即为答案。
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN=;
int n,m;
char mz[MAXN][MAXN];
int set_x[MAXN][MAXN],lenx;
int set_y[MAXN][MAXN],leny;
vector<int> arc[MAXN];
void build_graph()
{
memset(set_x,,sizeof(set_x));
memset(set_y,,sizeof(set_y));
lenx=;
leny=;
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
int tag=;
if(mz[i][j]=='*')
{
while(j<m&&mz[i][j]=='*')
{
if(!tag)
{
tag=;
lenx++;
}
set_x[i][j]=lenx;
j++;
}
}
}
}
for(int j=;j<m;j++)
{
for(int i=;i<n;i++)
{
int tag=;
if(mz[i][j]=='*')
{
while(i<n&&mz[i][j]=='*')
{
if(!tag)
{
tag=;
leny++;
}
set_y[i][j]=leny;
i++;
}
}
}
} for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
if(mz[i][j]=='*')
{
int u=set_x[i][j];
int v=set_y[i][j]+lenx;
arc[u].push_back(v);
arc[v].push_back(u);
}
}
}
} int match[MAXN],vis[MAXN];
bool dfs(int u)
{
for(int i=;i<arc[u].size();i++)
{
int to=arc[u][i];
if(!vis[to])
{
vis[to]=;
int w=match[to];
if(w==-||dfs(w))
{
match[to]=u;
match[u]=to;
return true;
}
}
}
return false;
}
int max_flow()
{
int ans=;
memset(match,-,sizeof(match));
for(int i=;i<=lenx;i++)
{
if(match[i]==-)
{
memset(vis,,sizeof(vis));
if(dfs(i)) ans++;
}
}
return ans;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=;i<MAXN;i++) arc[i].clear();
for(int i=;i<n;i++)
{
scanf("%s",mz[i]);
}
build_graph();
int res=max_flow();
printf("%d\n",res);
}
return ;
}
最新文章
- 计算机图形学 - 图形变换(opengl版)
- 整数划分问题-解法汇总(暂有DP-递归)
- java_easyui体系之DataGrid(4)[转]
- selenium如何操作cookies实现免登录
- 从MySQL到Redis 提升数据迁移的效率
- STC89c52RC 的EEPROM和AVR的EEPROM
- Tiny Spring 分析一
- ACM比赛(进制转换)
- AssetManager asset使用
- 吐槽CSDN--想赚钱想疯了--强行升级皮肤--增加广告位
- CCF-201509-2-日期计算
- Jmeter----【Mac电脑】环境配置与打开Jmeter界面
- tcp的4次挥手、三次握手
- [development][semaphore] 信号量/信号灯/信号标/旗语
- Python3基础 __len__,__getitem__ 记录列表中元素访问的次数 定制不可变序列,下标字典
- PHP原生:分享一个轻量级的缓存类=>;cache.php
- JVM调优总结 + jstat 分析
- Activiti进行时——企业工作流生命周期贯通 (zhuan)
- hdu3374(最小最大表示法以及kmp)
- how to be an efficient man