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

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
向QTextEdit拖放文件的方法及实现步骤

本文介绍了在使用QTextEdit时如何实现拖放文件的功能，包括相关的方法和实现步骤。通过重写dragEnterEvent和dropEvent函数，并结合QMimeData和QUrl等类，可以轻松实现向QTextEdit拖放文件的功能。详细的代码实现和说明可以参考本文提供的示例代码。 ... [详细]

蜡笔小新   2023-12-14 16:06:38

io
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新   2023-12-14 12:03:27

io
如何自行分析定位SAP BSP错误

The“BSPtag”Imentionedintheblogtitlemeansforexamplethetagchtmlb:configCelleratorbelowwhichi ... [详细]

蜡笔小新   2023-12-14 19:58:05

php
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新   2023-12-14 15:08:18

io
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新   2023-12-14 11:49:51

io
关于cuowu类的错误提示和使用AdjustmentListener的问题

本文讨论了一个关于cuowu类的问题，作者在使用cuowu类时遇到了错误提示和使用AdjustmentListener的问题。文章提供了16个解决方案，并给出了两个可能导致错误的原因。 ... [详细]

蜡笔小新   2023-12-13 22:09:56

io
P1651 塔 (动态规划) 的最大高度计算方法

本文介绍了P1651题目的描述和要求，以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术，将问题转化为求解差值的问题，并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]

蜡笔小新   2023-12-13 19:52:19

io
UVALive6575 Odd and Even Zeroes 数位dp+找规律

本文介绍了UVALive6575题目Odd and Even Zeroes的解法，使用了数位dp和找规律的方法。阶乘的定义和性质被介绍，并给出了一些例子。其中，部分阶乘的尾零个数为奇数，部分为偶数。 ... [详细]

蜡笔小新   2023-12-13 14:19:28

main
开发笔记：实验7的文件读写操作

本文介绍了使用C++的ofstream和ifstream类进行文件读写操作的方法，包括创建文件、写入文件和读取文件的过程。同时还介绍了如何判断文件是否成功打开和关闭文件的方法。通过本文的学习，读者可以了解如何在C++中进行文件读写操作。 ... [详细]

蜡笔小新   2023-12-12 17:48:18

io
JavaSE笔试题-接口、抽象类、多态等问题解答

本文解答了JavaSE笔试题中关于接口、抽象类、多态等问题。包括Math类的取整数方法、接口是否可继承、抽象类是否可实现接口、抽象类是否可继承具体类、抽象类中是否可以有静态main方法等问题。同时介绍了面向对象的特征，以及Java中实现多态的机制。 ... [详细]

蜡笔小新   2023-12-14 10:01:13

io
油田地块的划分和计数方法

本文介绍了一种划分和计数油田地块的方法。根据给定的条件，通过遍历和DFS算法，将符合条件的地块标记为不符合条件的地块，并进行计数。同时，还介绍了如何判断点是否在给定范围内的方法。 ... [详细]

蜡笔小新   2023-12-14 09:18:20

ip
使用多进程实现TCP服务端的优势和注意事项

本文介绍了为什么要使用多进程处理TCP服务端，多进程的好处包括可靠性高和处理大量数据时速度快。然而，多进程不能共享进程空间，因此有一些变量不能共享。文章还提供了使用多进程实现TCP服务端的代码，并对代码进行了详细注释。 ... [详细]

蜡笔小新   2023-12-13 18:25:30

foreach
关于Linq to sql 实现模糊查询 string数组

前景：当UI一个查询条件为多项选择，或录入多个条件的时候，比如查询所有名称里面包含以下动态条件，需要模糊查询里面每一项时比如是这样一个数组条件：newstring[]{兴业银行, ... [详细]

蜡笔小新   2023-12-13 09:34:59

ip
Java学习笔记之面向对象编程（OOP）

本文介绍了Java学习笔记中的面向对象编程（OOP）内容，包括OOP的三大特性（封装、继承、多态）和五大原则（单一职责原则、开放封闭原则、里式替换原则、依赖倒置原则）。通过学习OOP，可以提高代码复用性、拓展性和安全性。 ... [详细]

蜡笔小新   2023-12-13 08:44:30

ip
手机移动端HTML5和JavaScript如何实现视频上传和压缩视频质量？

本文讨论了在手机移动端如何使用HTML5和JavaScript实现视频上传并压缩视频质量，或者降低手机摄像头拍摄质量的问题。作者指出HTML5和JavaScript无法直接压缩视频，只能通过将视频传送到服务器端由后端进行压缩。对于控制相机拍摄质量，只有使用JAVA编写Android客户端才能实现压缩。此外，作者还解释了在交作业时使用zip格式压缩包导致CSS文件和图片音乐丢失的原因，并提供了解决方法。最后，作者还介绍了一个用于处理图片的类，可以实现图片剪裁处理和生成缩略图的功能。 ... [详细]

蜡笔小新   2023-12-12 15:58:44

金裕麟雯茂俊佑

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

Tags | 热门标签

javascript

bitmap

split

hashset

java

main

audio

golang

jar

io

vba

loops

netty

rsa

emoji

node.js

copy

chat

subset

php

cookie

hashcode

lua

ip

hook

spring

callback

regex

foreach

md5

RankList | 热门文章

1在syncdb时，django不会加载初始灯具 - django doesn't load initial fixtures while syncdb

2有没有哪家公司不修福报，不搞团建，不搞分享的，薪水还 OK，做完自己的事情就行了那种？

3访问控制_密钥对验证及TCP Wrappers访问控制

4ProGuard Spring Boot Maven 插件

5Linux——小技巧

6驱动开发（7）IRP与派遣函数

7SQL Server 2008中的代码安全（六）对称密钥加密分享

8为什么jupyterlab运行程序的时候会自动停止_JupyterLab史上最全详解，全网都在看，赶紧收藏...

9if(0 == 'hello') = true 求解释一下

10[VScode教程] VSCode 支持Emmet

11Oracle 安装时提示[INS13001] 环境不满足最低要求。

12Android提高之XML解析与生成实例详解

13《C++primer(第五版)》学习之路-第二章：变量和基本类型

14python如何使用gpu_python怎么利用gpu加速

15零基础java开发工程师视频教程全套,基础+进阶+项目实战(152G)