当前位置: 开发笔记 > 编程语言 > 正文

HDU5093Battleships(二分图最大匹配)

作者：金裕麟雯茂俊佑 | 来源：互联网 | 2023-10-12 19:50

题意：一个m行n列的图由#、*、o三种符号组成，分别代表冰山、海域、浮冰，问最多可放的炮舰数（要求满足以下条件）

题意&＃xff1a;一个m行n列的图由#、*、o三种符号组成&＃xff0c;分别代表冰山、海域、浮冰&＃xff0c;问最多可放的炮舰数&＃xff08;要求满足以下条件&＃xff09;

1、炮舰只可放在海域处

2、两个炮舰不能放在同一行或同一列(除非中间隔着一个或多个冰山)

分析&＃xff1a;

1、如果单纯只考虑不能放在同一行同一列&＃xff0c;那就是行号与列号的匹配&＃xff0c;原理与UVALive 6811 Irrigation Line(二分图最小点覆盖--匈牙利算法)相同。

2、但现在隔着冰山可以放置炮舰&＃xff0c;那假设某一行被冰山分隔成两部分&＃xff0c;这一行的前半部分和后半部分可以看做是两行&＃xff0c;再应用“行号”与“列号”的匹配的原理

3、既然要行号与列号匹配&＃xff0c;那就要分别按照行和列给图标号

举例如下&＃xff1a;

(1)若按行&＃xff0c;则将海域从1开始标号&＃xff0c;如果是连续的海域那标号相同&＃xff0c;若有冰山分隔&＃xff0c;标号加1.

PS:例如第三行22#3&＃xff0c;此处2是形式意义上的第二行&＃xff0c;因为有上述放置炮舰的原则&＃xff0c;可以理解为是可以放置炮舰的第2行&＃xff0c;而由于有冰山分隔&＃xff0c;所以这一行的前后互不干扰&＃xff0c;因此3可以理解为是可以放置炮舰的第3行

(2)按列同理

4、理论上讲海域可以放置炮舰&＃xff0c;也就是说&＃xff0c;有标号的地方可以放置炮舰&＃xff0c;每一个放置的地方都是一个行号与列号的匹配&＃xff0c;由此可得如下匹配

5、一条连线代表一个可放置的炮舰&＃xff0c;求最大匹配即可

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include<string>
#include
#include<set>
#include
#include
#include
#include
#include
#define Min(a, b) a #define Max(a, b) a
typedef long long ll;
typedef unsigned long long llu;
const int INT_INF &＃61; 0x3f3f3f3f;
const int INT_M_INF &＃61; 0x7f7f7f7f;
const ll LL_INF &＃61; 0x3f3f3f3f3f3f3f3f;
const ll LL_M_INF &＃61; 0x7f7f7f7f7f7f7f7f;
const int dr[] &＃61; {0, 0, -1, 1};
const int dc[] &＃61; {-1, 1, 0, 0};
const double pi &＃61; acos(-1.0);
const double eps &＃61; 1e-8;
const int MAXN &＃61; 50 &＃43; 10;
const int MAXT &＃61; 2500 &＃43; 10;
using namespace std;
char a[MAXN][MAXN];
int x[MAXN][MAXN];
int y[MAXN][MAXN];
int mp[MAXT][MAXT];
bool used[MAXT];
int match[MAXT];
int m, n, cnt1, cnt2;
void deal_row(){cnt1 &＃61; 1;for(int i &＃61; 0; i i){bool flag &＃61; false;for(int j &＃61; 0; j j){if(a[i][j] &＃61;&＃61; &＃39;*&＃39;){x[i][j] &＃61; cnt1;flag &＃61; true;}if(a[i][j] &＃61;&＃61; &＃39;#&＃39;){&＃43;&＃43;cnt1;flag &＃61; false;}}if(flag) &＃43;&＃43;cnt1;}
}
void deal_column(){cnt2 &＃61; 1;for(int i &＃61; 0; i i){bool flag &＃61; false;for(int j &＃61; 0; j j){if(a[j][i] &＃61;&＃61; &＃39;*&＃39;){y[j][i] &＃61; cnt2;flag &＃61; true;}if(a[j][i] &＃61;&＃61; &＃39;#&＃39;){&＃43;&＃43;cnt2;flag &＃61; false;}}if(flag) &＃43;&＃43;cnt2;}
}
bool Find(int x){for(int i &＃61; 1; i i){if(mp[x][i] && !used[i]){used[i] &＃61; true;if(!match[i] || Find(match[i])){match[i] &＃61; x;return true;}}}return false;
}
void solve(){int cnt &＃61; 0;for(int i &＃61; 1; i i){memset(used, false, sizeof used);if(Find(i)) &＃43;&＃43;cnt;}printf("%d\n", cnt);
}
int main(){int T;scanf("%d", &T);while(T--){memset(a, 0, sizeof a);memset(x, 0, sizeof x);memset(y, 0, sizeof y);memset(mp, 0, sizeof mp);memset(match, 0, sizeof match);scanf("%d%d", &m, &n);for(int i &＃61; 0; i i)scanf("%s", a[i]);deal_row();deal_column();for(int i &＃61; 0; i i){for(int j &＃61; 0; j j){if(a[i][j] &＃61;&＃61; &＃39;*&＃39;){mp[x[i][j]][y[i][j]] &＃61; 1;}}}solve();}return 0;
}

转:https://www.cnblogs.com/tyty-Somnuspoppy/p/6036855.html

ip

io

算法

include

string

ios

stream

go

queue

写下你的评论吧 !

吐个槽吧,看都看了

会员登录 | 用户注册

推荐阅读

io
深入理解KMP算法中的next数组：北大OJ 2406题解

本文详细探讨了KMP算法中next数组的构建及其应用，重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现，帮助读者更好地理解KMP算法的核心原理。 ... [详细]

蜡笔小新   2024-12-28 11:30:01

io
USACO 2014 Jan - Moolympics区间记录优化算法

题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]

蜡笔小新   2024-12-27 18:14:31

数组
C++ 中的数组与动态数组初始化

本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度，而 vector 是一种可扩展的容器，允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景，并提供了代码示例以加深理解。 ... [详细]

蜡笔小新   2024-12-26 15:38:03

window
HTTP请求与响应机制详解

本文深入探讨了HTTP请求和响应对象的使用，详细介绍了如何通过响应对象向客户端发送数据、处理中文乱码问题以及常见的HTTP状态码。此外，还涵盖了文件下载、请求重定向、请求转发等高级功能。 ... [详细]

蜡笔小新   2024-12-23 20:40:08

foreach
java8新特性学习笔记

使用lambda表达式排序Collections.sort(temp,(Stringa,Stringb)-{returnb.compareTo(a);});Collections ... [详细]

蜡笔小新   2024-12-23 14:41:31

nodejs
Node.js 中可写流的默认编码设置方法

本文介绍了如何在 Node.js 中使用 `setDefaultEncoding` 方法为可写流设置默认编码，并提供了详细的语法说明和示例代码。 ... [详细]

蜡笔小新   2024-12-22 10:44:58

io
Mathematica 12.3.1 中英文版正式发布，附新功能介绍

历经三十年的开发，Mathematica 已成为技术计算领域的标杆，为全球的技术创新者、教育工作者、学生及其他用户提供了一个领先的计算平台。最新版本 Mathematica 12.3.1 增加了多项核心语言、数学计算、可视化和图形处理的新功能。 ... [详细]

蜡笔小新   2024-12-22 09:34:59

io
Java 中 Writer flush()方法，示例

Java 中 Writer flush()方法，示例 ... [详细]

蜡笔小新   2024-12-28 06:41:52

case
java编写的简易计算器

主要用了2个类来实现的，话不多说，直接看运行结果，然后在奉上源代码1.Index.javaimportjava.awt.Color;im ... [详细]

蜡笔小新   2024-12-27 18:18:10

request
使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表

本文介绍了一段通用代码示例，该代码不仅能够操作 Azure Active Directory (AAD)，还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级：AAD 和 Subscription。 ... [详细]

蜡笔小新   2024-12-27 16:07:12

case
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]

蜡笔小新   2024-12-26 20:04:36

io
寻找满足特定条件的整数N的最大和(a+b)

本文探讨了如何在给定整数N的情况下，找到两个不同的整数a和b，使得它们的和最大，并且满足特定的数学条件。 ... [详细]

蜡笔小新   2024-12-26 19:26:18

hash
不确定性|放入_华为机试题 HJ9提取不重复的整数

不确定性|放入_华为机试题 HJ9提取不重复的整数 ... [详细]

蜡笔小新   2024-12-24 16:13:05

request
Servlet 表单处理：GET 和 POST 请求的深入解析

本文详细探讨了HTML表单中GET和POST请求的区别，包括它们的工作原理、数据传输方式、安全性及适用场景。同时，通过实例展示了如何在Servlet中处理这两种请求。 ... [详细]

蜡笔小新   2024-12-23 18:09:59

case
Android 自定义绘图板应用

本文介绍如何使用 Android 的 Canvas 和 View 组件创建一个简单的绘图板应用程序，支持触摸绘画和保存图片功能。 ... [详细]

蜡笔小新   2024-12-23 10:12:53

金裕麟雯茂俊佑

这个家伙很懒，什么也没留下！

Tags | 热门标签

emoji

runtime

bash

cPlusPlus

web

stream

default

hook

testing

数组

post

chat

jar

io

request

datetime

case

nodejs

callback

select

cookie

hash

audio

foreach

byte

export

subset

window

vba

bytecode

RankList | 热门文章

1将多个excel合并成一个excel

2PS抠图后怎么把原图修复好.

3联合舰队的覆灭（4）

4Excel实现二级菜单联动

5终于理解了什么叫装忙一族

6辞职后的感想!

7ERP系统验收时测试流程方法及内容[3]

8电脑屏幕字体模糊怎么调整清晰

9arm汇编中ldr指令中出现的等号作用

10无人超市缤果盒子软件

11《区块链100问》第75集：大零币Zcash是什么？

12word2016怎么显示修改痕迹

13毕业后的五年拉开大家差距的原因

14mathtype6.9安装包和激活码支持2016,2013下载

15EXCEL 2010怎样固定表头