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

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

写下你的评论吧 !

吐个槽吧,看都看了

会员登录 | 用户注册

推荐阅读

ip
CUGB图论专题：排水系统中的最大流问题 - EK与Dinic算法解析

本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率，使用经典的EK（Edmonds-Karp）和Dinic算法进行求解。 ... [详细]

蜡笔小新   2024-12-25 17:47:23

get
Java并发编程：LinkedBlockingQueue的实际应用

本文介绍了Java并发库中的阻塞队列（BlockingQueue）及其典型应用场景。通过具体实例，展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递，并结合线程池和原子类优化性能。 ... [详细]

蜡笔小新   2024-12-27 18:51:49

ip
丽江客栈选择问题

本文介绍了一道经典的算法题，题目涉及在丽江河边的n家特色客栈中选择住宿方案。两位游客希望住在色调相同的两家客栈，并在晚上选择一家最低消费不超过p元的咖啡店小聚。我们将详细探讨如何计算满足条件的住宿方案总数。 ... [详细]

蜡笔小新   2024-12-22 20:15:25

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

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

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

ip
分页插件3指定到某一页

前言--页数多了以后需要指定到某一页（只做了功能，样式没有细调）html ... [详细]

蜡笔小新   2024-12-27 15:19:01

ip
Linux 网卡绑定的七种工作模式详解

本文深入探讨了Linux系统中网卡绑定（bonding）的七种工作模式。网卡绑定技术通过将多个物理网卡组合成一个逻辑网卡，实现网络冗余、带宽聚合和负载均衡，在生产环境中广泛应用。文章详细介绍了每种模式的特点、适用场景及配置方法。 ... [详细]

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

ip
递推算法与大数处理

本问题探讨了在特定条件下排列儿童队伍的方法数量。题目要求计算满足条件的队伍排列总数，并使用递推算法和大数处理技术来解决这一问题。 ... [详细]

蜡笔小新   2024-12-23 12:18:55

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

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

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

get
MyBatis 动态 SQL 详解与应用

本文深入探讨 MyBatis 中动态 SQL 的使用方法，包括 if/where、trim 自定义字符串截取规则、choose 分支选择、封装查询和修改条件的 where/set 标签、批量处理的 foreach 标签以及内置参数和 bind 的用法。 ... [详细]

蜡笔小新   2024-12-27 16:20:10

ip
2023年全球运营商网络设备市场预计突破202亿美元

尽管某些细分市场如WAN优化表现不佳，但全球运营商路由器和交换机市场持续增长。根据最新研究，该市场预计在2023年达到202亿美元的规模。 ... [详细]

蜡笔小新   2024-12-27 12:44:44

const
Linux设备驱动程序：异步时间操作与调度机制

本文介绍了Linux内核中的几种异步延迟操作方法，包括内核定时器、tasklet机制和工作队列。这些机制允许在未来的某个时间点执行任务，而无需阻塞当前线程，从而提高系统的响应性和效率。 ... [详细]

蜡笔小新   2024-12-26 08:55:03

ip
POJ 3259 Bellman-Ford算法实现

本文提供了使用Java实现Bellman-Ford算法解决POJ 3259问题的代码示例，详细解释了如何通过该算法检测负权环来判断时间旅行的可能性。 ... [详细]

蜡笔小新   2024-12-25 20:03:22

ip
微软Exchange服务器遭遇2022年版“千年虫”漏洞

微软Exchange服务器在新年伊始遭遇了一个类似于‘千年虫’的日期处理漏洞，导致邮件传输受阻。该问题主要影响配置了FIP-FS恶意软件引擎的Exchange 2016和2019版本。 ... [详细]

蜡笔小新   2024-12-25 14:08:03

ip
Tetris 排名系统 (拓扑排序与并查集的应用)

本题旨在通过给定的评级信息，利用拓扑排序和并查集算法来确定全球 Tetris 高手排行榜。题目要求判断是否可以根据提供的信息生成一个明确的排名表，或者是否存在冲突或信息不足的情况。 ... [详细]

蜡笔小新   2024-12-24 21:03:51

get
C# XNA 中实现自定义 3x3 矩阵类：MMatrix33

本文介绍了如何在 C# 和 XNA 框架中实现一个自定义的 3x3 矩阵类（MMatrix33），旨在深入理解矩阵运算及其应用场景。该类参考了 AS3 Starling 和其他相关资源，以确保算法的准确性和高效性。 ... [详细]

蜡笔小新   2024-12-21 17:27:57

金裕麟雯茂俊佑

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

Tags | 热门标签

object

jar

httpclient

python

dagger

export

email

ascii

settings

fetch

cPlusPlus

usb

list

netty

const

header

sum

cmd

search

flutter

web3

import

get

md5

dll

bitmap

vba

uri

ip

regex

RankList | 热门文章

1深入理解Flask：项目配置详解

2Hadoop发行版本选择指南：技术解析与应用实践

3采用IKE方式建立IPsec安全隧道

4丽江客栈选择问题

5Angular中如何监听通过ngFor生成的DOM元素的事件

6SDCMS全局与循环标签详解

7TensorFlow 2.0 实战：多层感知机（MLP）网络入门

8腾讯云服务器上配置 phpMyAdmin 的详细步骤

9有C和C++基础，如何提高面向对象的类的设计能力？

10深入理解 Android 资源管理与使用

11如何查询拥有多个特定BookID的单个会员

12使用.NET Framework实现图形移动功能

13MySQL InnoDB Double Write机制详解

14CodeChef 2014 April Challenge - Chef的最终对决：数据结构与整体二分的应用

15深入理解 .NET 中的中间件