HDU 4185 Oil Skimming 【最大匹配】

时间:2020-12-30 23:52:50

<题目链接>

题目大意:

给你一张图,图中有 '*' , '.' 两点,现在每次覆盖相邻的两个 '#' ,问最多能够覆盖几次。

解题分析:

无向图二分匹配的模板题,每个'#'点与周围四个方向的'#'建立匹配关系,然后用匈牙利跑一遍,因为匹配的两点各会进行相互匹配一次,所以最大匹配数为ans/2。

 #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int N=+; //本题数据中'#'数量较少,开到600都能AC
char mpa[][];
int n,vN,vM;
int g[N][N],cnt[][],vis[N],match[N];
bool dfs(int x){
for(int i=;i<=vM;i++){
if(g[x][i]&&!vis[i]){
vis[i]=;
if(match[i]==-||dfs(match[i])){
match[i]=x;
return true;
}
}
}
return false;
}
int Hungary(){
int ans=;
memset(match,-,sizeof(match));
for(int i=;i<=vN;i++){
memset(vis,,sizeof(vis));
if(dfs(i))ans++;
}
return ans;
}
int main(){
int T;scanf("%d",&T);
int ncase=;
while(T--){
scanf("%d",&n);
int pos=;
for(int i=;i<=n;i++){
scanf("%s",mpa[i]+);
for(int j=;j<=n;j++)
if(mpa[i][j]=='#')cnt[i][j]=++pos; //给所有的'#'分配编号
}
memset(g,,sizeof(g));
//将该点与其周围四个方向的'#'都建立匹配关系
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(mpa[i][j]!='#')continue;
if(i->=&&mpa[i-][j]=='#')g[cnt[i][j]][cnt[i-][j]]=;
if(j->=&&mpa[i][j-]=='#')g[cnt[i][j]][cnt[i][j-]]=;
if(i+<=n&&mpa[i+][j]=='#')g[cnt[i][j]][cnt[i+][j]]=;
if(j+<=n&&mpa[i][j+]=='#')g[cnt[i][j]][cnt[i][j+]]=;
}
}
vN=vM=pos;
int ans=Hungary(); //求出最大匹配数
printf("Case %d: %d\n",++ncase,ans/); //因为匹配的两点会相互各进行一次匹配,所以这里要除以2
}
return ;
}

2018-11-14

HDU 4185 Oil Skimming 【最大匹配】的更多相关文章

  1. HDU 4185 ——Oil Skimming——————【最大匹配、方格的奇偶性建图】

    Oil Skimming Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit ...

  2. hdu 4185 Oil Skimming(二分图匹配 经典建图&plus;匈牙利模板)

    Problem Description Thanks to a certain "green" resources company, there is a new profitab ...

  3. 4185 Oil Skimming 最大匹配 奇偶建图

    题目大意: 统计相邻(上下左右)的‘#’的对数. 解法: 与题目hdu1507 Uncle Tom's Inherited Land*类似,需要用奇偶建图.就是行+列为奇数的作为X集合,偶尔作为Y集合 ...

  4. HDU 4185 Oil Skimming

    题目大意:在一个N*N的矩阵里寻找最多有多少个“##”(横着竖着都行).     题目分析:重新构图,直接以相邻的两个油井算中间算以条边,然后进行匹配,看看两两之间最多能匹配多少对. #include ...

  5. HDU4185 Oil Skimming —— 最大匹配

    题目链接:https://vjudge.net/problem/HDU-4185 Oil Skimming Time Limit: 2000/1000 MS (Java/Others)    Memo ...

  6. Oil Skimming HDU - 4185(匹配板题)

    Oil Skimming Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Tota ...

  7. HDU4185:Oil Skimming(二分图最大匹配)

    Oil Skimming Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Tota ...

  8. 匈牙利算法求最大匹配(HDU-4185 Oil Skimming)

    如下图:要求最多可以凑成多少对对象 大佬博客: https://blog.csdn.net/cillyb/article/details/55511666 https://blog.csdn.net/ ...

  9. J - Oil Skimming 二分图的最大匹配

    Description Thanks to a certain "green" resources company, there is a new profitable indus ...

随机推荐

  1. JS基本概念

    1.一切(变量.函数名.操作符)都区分大小写 2.标识符:第一个字符必须为字母.下划线或者美元符号,其他字符可以是字母.下划线.美元符号或者数字 3.数据类型 1)undefined:用var声明的变 ...

  2. 286&period;&Tab;Walls and Gates

    题目: You are given a m x n 2D grid initialized with these three possible values. -1 - A wall or an ob ...

  3. Localizing Astah – Chinese version&lpar;simplified&rpar; is now available&excl;

    Thanks to Abbey, now GUI in Astah Community can be shown in Chinese. As Abbey created Chinese one, a ...

  4. 数据挖掘学习笔记:挖掘频繁模式、关联和相关&lbrack;ZZ&rsqb;

    所 谓挖掘频繁模式,关联和相关,即指在出现的数据集中找到一个经常出现的序列模式或者是一个经常出现的数据结构.就像搞CPU设计的人知道,Cache的预 取机制有流预取和指针预取,前者就是发现流模式,即发 ...

  5. &lbrack;转&rsqb;jQuery EasyUI 扩展-- 主题(Themes)

    主题(Themes)允许您改变站点的外观和感观.使用主题可以节省设计的时间,让您腾出更多的时间进行开发.您也可以创建一个已有主题的子主题. 主题生成器(Theme Builder) jQuery UI ...

  6. csdn 博客&comma;你很努力&comma;有人帮你-2015年03一个月17日本

    今天泛化 开始使用简书 正则表达式的博客写了两篇文章 回顾 Core Data 基本使用 总结 Xcode6新特性 简单聊聊 简书,事实上一開始学 MarkDown 语法的时候,已经用了,但是,一直认 ...

  7. Bear and Friendship Condition-HZUN寒假集训

    Bear and Friendship Condition time limit per test 1 secondmemory limit per test 256 megabytesinput s ...

  8. Go接口interface

    目录 接口是什么? interface类型 空接口(interface{}) interface函数参数 interface变量存储的类型 类型断言 嵌入interface 接口是什么? Go 语言不 ...

  9. REdis主挂掉后复制节点才起来会如何?

    结论: 这种情况下复制节点(即从节点)无法提升为主节点,复制节点会一直尝试和主节点建立连接,直接成功.主节点恢复后,复制节点仍然保持为复制节点,并不会成为主节点. 复制节点无法提升为主节点的原因是复制 ...

  10. python模块:xml&period;etree&period;ElementTree

    """Lightweight XML support for Python. XML is an inherently hierarchical data format, ...