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

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

写下你的评论吧 !

吐个槽吧,看都看了

会员登录 | 用户注册

推荐阅读

list
Codeforces Round #321 (Div. 2) Kefa and Dishes 状压+spfa

本文介绍了Codeforces Round #321 (Div. 2)比赛中的问题Kefa and Dishes，通过状压和spfa算法解决了这个问题。给定一个有向图，求在不超过m步的情况下，能获得的最大权值和。点不能重复走。文章详细介绍了问题的题意、解题思路和代码实现。 ... [详细]

蜡笔小新   2023-12-11 10:37:34

list
hdu 5439（找规律）的数列求和问题

本文讨论了一个数列求和问题，该数列按照一定规律生成。通过观察数列的规律，我们可以得出求解该问题的算法。具体算法为计算前n项i*f[i]的和，其中f[i]表示数列中有i个数字。根据参考的思路，我们可以将算法的时间复杂度控制在O(n)，即计算到5e5即可满足1e9的要求。 ... [详细]

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

list
九度OnlineJudge之1002：Grading问题的解决方法

本文介绍了九度OnlineJudge中的1002题目“Grading”的解决方法。该题目要求设计一个公平的评分过程，将每个考题分配给3个独立的专家，如果他们的评分不一致，则需要请一位裁判做出最终决定。文章详细描述了评分规则，并给出了解决该问题的程序。 ... [详细]

蜡笔小新   2023-12-14 13:00:09

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

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

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

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

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

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

bit
李逍遥寻找仙药的迷阵之旅

本文讲述了少年李逍遥为了救治婶婶的病情，前往仙灵岛寻找仙药的故事。他需要穿越一个由M×N个方格组成的迷阵，有些方格内有怪物，有些方格是安全的。李逍遥需要避开有怪物的方格，并经过最少的方格，找到仙药。在寻找的过程中，他还会遇到神秘人物。本文提供了一个迷阵样例及李逍遥找到仙药的路线。 ... [详细]

蜡笔小新   2023-12-12 13:59:33

bit
Codeforces 1294A题解：Collecting Coins整除+不整除问题解析

本文为Codeforces 1294A题目的解析，主要讨论了Collecting Coins整除+不整除问题。文章详细介绍了题目的背景和要求，并给出了解题思路和代码实现。同时提供了在线测评地址和相关参考链接。 ... [详细]

蜡笔小新   2023-12-14 21:14:58

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

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

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

bit
二叉树层序创建问题的解决方法

本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体，实现了入队和出队操作，并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]

蜡笔小新   2023-12-13 18:20:50

bit
CF：3D City Model（小思维）问题解析和代码实现

本文通过解析CF：3D City Model问题，介绍了问题的背景和要求，并给出了相应的代码实现。该问题涉及到在一个矩形的网格上建造城市的情景，每个网格单元可以作为建筑的基础，建筑由多个立方体叠加而成。文章详细讲解了问题的解决思路，并给出了相应的代码实现供读者参考。 ... [详细]

蜡笔小新   2023-12-13 14:17:11

php
C++中的三角函数计算及其应用

本文介绍了C++中的三角函数的计算方法和应用，包括计算余弦、正弦、正切值以及反三角函数求对应的弧度制角度的示例代码。代码中使用了C++的数学库和命名空间，通过赋值和输出语句实现了三角函数的计算和结果显示。通过学习本文，读者可以了解到C++中三角函数的基本用法和应用场景。 ... [详细]

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

php
[CF949D]Curfew 二分答案是个不错的开头，困难部分在于如何检查

本文介绍了一个题目的解法，通过二分答案来解决问题，但困难在于如何进行检查。文章提供了一种逃逸方式，通过移动最慢的宿管来锁门时跑到更居中的位置，从而使所有合格的寝室都居中。文章还提到可以分开判断两边的情况，并使用前缀和的方式来求出在任意时刻能够到达宿管即将锁门的寝室的人数。最后，文章提到可以改成O(n)的直接枚举来解决问题。 ... [详细]

蜡笔小新   2023-12-13 09:08:55

php
3.223.28周学习总结中的贪心作业收获及困惑

本文是对3.223.28周学习总结中的贪心作业进行总结，作者在解题过程中参考了他人的代码，但前提是要先理解题目并有解题思路。作者分享了自己在贪心作业中的收获，同时提到了一道让他困惑的题目，即input details部分引发的疑惑。 ... [详细]

蜡笔小新   2023-12-13 03:42:02

bit
微软头条实习生分享深度学习自学指南

本文介绍了一位微软头条实习生自学深度学习的经验分享，包括学习资源推荐、重要基础知识的学习要点等。作者强调了学好Python和数学基础的重要性，并提供了一些建议。 ... [详细]

蜡笔小新   2023-12-14 20:58:32

bit
云原生边缘计算之KubeEdge简介及功能特点

本文介绍了云原生边缘计算中的KubeEdge系统，该系统是一个开源系统，用于将容器化应用程序编排功能扩展到Edge的主机。它基于Kubernetes构建，并为网络应用程序提供基础架构支持。同时，KubeEdge具有离线模式、基于Kubernetes的节点、群集、应用程序和设备管理、资源优化等特点。此外，KubeEdge还支持跨平台工作，在私有、公共和混合云中都可以运行。同时，KubeEdge还提供数据管理和数据分析管道引擎的支持。最后，本文还介绍了KubeEdge系统生成证书的方法。 ... [详细]

蜡笔小新   2023-12-14 16:49:01

金裕麟雯茂俊佑

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

Tags | 热门标签

keyword

testing

match

uri

erlang

subset

dagger

perl

split

integer

php

controller

default

heap

expression

instance

emoji

plugins

vbscript

php8

substring

cPlusPlus

triggers

metadata

install

cookie

typescript

hashtable

php7

bit

RankList | 热门文章

1chardet字符集检测模块

2笔记本win10如何设置打印机“共享”？

3Pytorch创建模型的多种方法

4Halcon2022年3月各版本License下载

5Elam的caffe笔记之配置篇（一）：CentOS6.5编译安装gcc4.8.2

6源码与课件获取

7java四舍五入BigDecimal和js保留小数点两位

8《送张郎中副使赴泽潞》翻译原文赏析诗人唐姚合

9网络基础知识!端口对照,常用命令!

10内蒙古工业大学排名2022最新排名表：全国排多少？第几位？

11什么是职业经理人

12SIM7X00 Sleep mode 和 Wakeup mode

13网络基础 http 会话(session)详解

14西伯利亚声卡怎么设置？

15流浪气球？ChatGPT这样回答，我惊了