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

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

写下你的评论吧 !

吐个槽吧,看都看了

会员登录 | 用户注册

推荐阅读

int
AOJ.863 分配书籍问题（深度优先搜索算法）

题目解析给定 n 个人和 n 种书籍，每个人都有一个包含自己喜好的书籍列表。目标是计算出满足以下条件的分配方案数量：1. 每个人都必须获得他们喜欢的书籍；2. 每本书只能分配给一个人。通过使用深度优先搜索算法，可以系统地探索所有可能的分配组合，确保每个分配方案都符合上述条件。该方法能够有效地处理这类组合优化问题，找到所有可行的解。 ... [详细]

蜡笔小新   2024-11-09 20:10:25

int
字节流(InputStream和OutputStream)，字节流读写文件，字节流的缓冲区，字节缓冲流

字节流抽象类InputStream和OutputStream是字节流的顶级父类所有的字节输入流都继承自InputStream，所有的输出流都继承子OutputStreamInput ... [详细]

蜡笔小新   2024-11-12 14:07:25

int
Android 源代码解析系列（一）：init.c 文件详解

本文详细解析了 Android 系统启动过程中的核心文件 `init.c`，探讨了其在系统初始化阶段的关键作用。通过对 `init.c` 的源代码进行深入分析，揭示了其如何管理进程、解析配置文件以及执行系统启动脚本。此外，文章还介绍了 `init` 进程的生命周期及其与内核的交互方式，为开发者提供了深入了解 Android 启动机制的宝贵资料。 ... [详细]

蜡笔小新   2024-11-10 00:35:48

int
洛谷 P1531 我讨厌它 —— 线段树实现

本文介绍如何使用线段树解决洛谷 P1531 我讨厌它问题，重点在于单点更新和区间查询最大值。 ... [详细]

蜡笔小新   2024-11-12 21:27:38

int
单片微机原理P3：80C51外部拓展系统

　　外部拓展其实是个相对来说很好玩的章节，可以真正开始用单片机写程序了，比较重要的是外部存储器拓展，81C55拓展，矩阵键盘，动态显示，DAC和ADC。0.IO接口电路概念与存 ... [详细]

蜡笔小新   2024-11-12 19:51:29

int
c/c++常用代码doc,ppt,xls文件格式转PDF格式[转]

[转]doc,ppt,xls文件格式转PDF格式http:blog.csdn.netlee353086articledetails7920355确实好用。需要注意的是#import ... [详细]

蜡笔小新   2024-11-12 16:19:40

include
Unity中简易广告牌着色器的实现

本文详细介绍了如何在Unity中实现一个简单的广告牌着色器，帮助开发者更好地理解和应用这一技术。 ... [详细]

蜡笔小新   2024-11-12 14:50:43

int
如何在Java中使用DButils类

这期内容当中小编将会给大家带来有关如何在Java中使用DButils类，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。D ... [详细]

蜡笔小新   2024-11-12 13:46:11

int
检查在所有可能的“？”替换中，给定的二进制字符串中是否出现子字符串“10”带 1 或 0

检查在所有可能的“？”替换中，给定的二进制字符串中是否出现子字符串“10”带 1 或 0 ... [详细]

蜡笔小新   2024-11-12 11:35:01

int
poj 3352 Road Construction

poj 3352 Road Construction ... [详细]

蜡笔小新   2024-11-12 11:24:39

int
ANSI C中实现动态分配二维数组的方法

本文介绍了一种在ANSI C中动态分配二维数组的方法。通过创建指针数组并为每个指针分配连续空间，可以灵活地管理内存。文章还讨论了一些常见的错误和注意事项。 ... [详细]

蜡笔小新   2024-11-12 08:49:29

int
详解 Qt 串口通信程序全程图文（4）

Qt串口通信程序全程图文是本文介绍的内容，本文一开始先讲解对程序的改进，在文章最后将要讲解一些重要问题。1、在窗口中加入一些组合框ComboBox&# ... [详细]

蜡笔小新   2024-11-12 00:05:00

include
Xcode 多项目联合调试技巧与实践

在软件开发过程中，经常需要将多个项目或模块进行集成和调试，尤其是当项目依赖于第三方开源库（如Cordova、CocoaPods）时。本文介绍了如何在Xcode中高效地进行多项目联合调试，分享了一些实用的技巧和最佳实践，帮助开发者解决常见的调试难题，提高开发效率。 ... [详细]

蜡笔小新   2024-11-11 18:24:27

int
深入解析Properties属性类及其应用

属性类 `Properties` 是 `Hashtable` 类的子类，用于存储键值对形式的数据。该类在 Java 中广泛应用于配置文件的读取与写入，支持字符串类型的键和值。通过 `Properties` 类，开发者可以方便地进行配置信息的管理，确保应用程序的灵活性和可维护性。此外，`Properties` 类还提供了加载和保存属性文件的方法，使其在实际开发中具有较高的实用价值。 ... [详细]

蜡笔小新   2024-11-11 13:55:43

int
如何将TS文件转换为M3U8直播流：HLS与M3U8格式详解

在视频传输领域，MP4虽然常见，但在直播场景中直接使用MP4格式存在诸多问题。例如，MP4文件的头部信息（如ftyp、moov）较大，导致初始加载时间较长，影响用户体验。相比之下，HLS（HTTP Live Streaming）协议及其M3U8格式更具优势。HLS通过将视频切分成多个小片段，并生成一个M3U8播放列表文件，实现低延迟和高稳定性。本文详细介绍了如何将TS文件转换为M3U8直播流，包括技术原理和具体操作步骤，帮助读者更好地理解和应用这一技术。 ... [详细]

蜡笔小新   2024-11-11 12:12:04

金裕麟雯茂俊佑

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

Tags | 热门标签

settings

grid

version

runtime

md5

php8

metadata

erlang

hashcode

match

emoji

vbscript

split

command

python2

string

tags

frameworks

bytecode

spring

main

include

httpclient

client

fetch

hook

int

eval

iostream

hashtable

RankList | 热门文章

1python语言必背代码好用到哭！请记住这20段Python代码

2Vscode使用python开发教程(怎么使用vscode编写python)

3photoSwipe插件使用

4服务器端分页

5开发笔记:棋盘(BFS)

6分分钟搞懂JS-闭包函数

720165231 201720182《Java程序设计》课程总结

8UML时序图添加用户

9java语法糖之jdk迭代的新特性汇总

10基于PHP+小程序(MINA框架)+Mysql数据库的电子书阅读小程序系统设计与实现

11面向动态防御的大数据安全技术研究

12Git 标签（版本号）

13shell：828

14php中配置Discuz!

15php按需加载,apache加载php