【洛谷4251】[SCOI2015]小凸玩矩阵（二分答案，二分图匹配）

作者：淡水鱼yw灬s | 来源：互联网 | 2023-10-13 21:37

题面传送门Solution看到什么最大值最小肯定二分啊。check直接跑一个二分图匹配就好了。orzztl！！！代码实现*mail:mle

题面

传送门

Solution

看到什么最大值最小肯定二分啊。
check直接跑一个二分图匹配就好了。
orz ztl&＃xff01;&＃xff01;&＃xff01;

代码实现

/*mail: mleautomaton&＃64;foxmail.comauthor: MLEAutoMatonThis Code is made by MLEAutoMaton */ #include #include #include #include #include #include #include #include #include using namespace std; #define ll long long #define re register #define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout) inline int gi() {int f&＃61;1,sum&＃61;0;char ch&＃61;getchar();while(ch>&＃39;9&＃39; || ch<&＃39;0&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)f&＃61;-1;ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39; && ch<&＃61;&＃39;9&＃39;){sum&＃61;(sum<<3)&＃43;(sum<<1)&＃43;ch-&＃39;0&＃39;;ch&＃61;getchar();}return f*sum; } const int N&＃61;500010,M&＃61;2000010,Inf&＃61;1e9&＃43;10; struct node {int to,nxt,w; }e[M<<1]; int front[N],cnt,s,t,dep[N],n,m,k,a[510][510]; void Add(int u,int v,int w) {e[cnt]&＃61;(node){v,front[u],w};front[u]&＃61;cnt&＃43;&＃43;;e[cnt]&＃61;(node){u,front[v],0};front[v]&＃61;cnt&＃43;&＃43;; } void clear(){memset(front,-1,sizeof(front));cnt&＃61;0;} queueQ; bool bfs() {Q.push(s);memset(dep,0,sizeof(dep));dep[s]&＃61;1;while(!Q.empty()){int u&＃61;Q.front();Q.pop();for(int i&＃61;front[u];~i;i&＃61;e[i].nxt){int v&＃61;e[i].to;if(e[i].w && !dep[v]){dep[v]&＃61;dep[u]&＃43;1;Q.push(v);}}}return dep[t]; } int dfs(int u,int flow) {if(u&＃61;&＃61;t || !flow)return flow;for(int i&＃61;front[u];~i;i&＃61;e[i].nxt){int v&＃61;e[i].to;if(e[i].w && dep[v]&＃61;&＃61;dep[u]&＃43;1){int di&＃61;dfs(v,min(flow,e[i].w));if(di){e[i].w-&＃61;di;e[i^1].w&＃43;&＃61;di;return di;}else dep[v]&＃61;0;}}return 0; } int dinic() {int flow&＃61;0;while(bfs())while(int d&＃61;dfs(s,Inf))flow&＃43;&＃61;d;return flow; } void build(int mid) {for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)Add(s,i,1);for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;)Add(i&＃43;n,t,1);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;)if(a[i][j]<&＃61;mid)Add(i,j&＃43;n,1); } int main() {n&＃61;gi();m&＃61;gi();k&＃61;gi();clear();int Max&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;){a[i][j]&＃61;gi();Max&＃61;max(Max,a[i][j]);}int l&＃61;0,r&＃61;Max,ans&＃61;0;t&＃61;n&＃43;m&＃43;1;while(l<&＃61;r){int mid&＃61;(l&＃43;r)>>1;clear();build(mid);if(dinic()>&＃61;n-k&＃43;1){r&＃61;mid-1;ans&＃61;mid;}else l&＃61;mid&＃43;1;}printf("%d\n",ans);return 0; }

转:https://www.cnblogs.com/mle-world/p/10568222.html

推荐阅读

char
POJ 2777：线段树的懒惰更新策略分析与实现

题目链接：POJ 2777。问题描述：给定一个区域，需要进行多次涂色操作，并在每次操作后查询某个区间内的不同颜色数量。解决方案：由于题目中颜色种类不超过30种，可以利用线段树的懒惰更新策略来高效处理这些操作。通过懒惰标记，避免了不必要的节点更新，从而显著提高了算法的效率。此外，该方法还能有效应对大规模数据输入，确保在合理的时间内完成所有操作。 ... [详细]

蜡笔小新 2024-11-03 15:22:44
bit
寒假作业解析：第三周 2月12日第7题

尽快完成之前的练习任务！每日一练2.1 Problem A Laurenty and Shop 的题目要求是选择两条不同的路线以最小化总的等待时间。简要分析：通过对比不同路线的等待时间，可以找到最优解。此问题可以通过动态规划或贪心算法来解决，具体取决于路线的复杂性和约束条件。 ... [详细]

蜡笔小新 2024-11-06 14:33:36
bit
BZOJ4240 Gym 102082G：贪心算法与树状数组的综合应用

BZOJ4240 Gym 102082G 题目 "有趣的家庭菜园" 结合了贪心算法和树状数组的应用，旨在解决在有限时间和内存限制下高效处理复杂数据结构的问题。通过巧妙地运用贪心策略和树状数组，该题目能够在 10 秒的时间限制和 256MB 的内存限制内，有效处理大量输入数据，实现高性能的解决方案。提交次数为 756 次，成功解决次数为 349 次，体现了该题目的挑战性和实际应用价值。 ... [详细]

蜡笔小新 2024-11-01 09:27:15
sum
优化后的标题：洛谷P3239 [HNOI2015] 亚瑟王算法详解与实现

题目描述：小K不幸被LL邪教洗脑，洗脑程度之深使他决定彻底脱离这个邪教。在最终离开前，他计划再进行一次亚瑟王游戏。作为最后一战，他希望这次游戏能够尽善尽美。众所周知，亚瑟王游戏的结果很大程度上取决于运气，但通过合理的策略和算法优化，可以提高获胜的概率。本文将详细解析洛谷P3239 [HNOI2015] 亚瑟王问题，并提供具体的算法实现方法，帮助读者更好地理解和应用相关技术。 ... [详细]

蜡笔小新 2024-10-30 19:46:06
search
NOIP2000单词接龙题目解析与学习心得

NOIP2000的单词接龙问题与常见的成语接龙游戏有异曲同工之妙。题目要求在给定的一组单词中，从指定的起始字母开始，构建最长的“单词链”。每个单词在链中最多可出现两次。本文将详细解析该题目的解法，并分享学习过程中的心得体会。 ... [详细]

蜡笔小新 2024-11-08 14:01:31
object
单链表的高效遍历及性能优化策略

本文探讨了单链表的高效遍历方法及其性能优化策略。在单链表的数据结构中，插入操作的时间复杂度为O(n)，而遍历操作的时间复杂度为O(n^2)。通过在 `LinkList.h` 和 `main.cpp` 文件中对单链表进行封装，我们实现了创建和销毁功能的优化，提高了单链表的使用效率。此外，文章还介绍了几种常见的优化技术，如缓存节点指针和批量处理，以进一步提升遍历性能。 ... [详细]

蜡笔小新 2024-11-07 15:55:20
bit
洛谷 P1344 坏牛奶追踪问题（最小割算法应用）

在洛谷 P1344 的坏牛奶追踪问题中，第一问要求计算最小割，而第二问则需要找到割边数量最少的最小割。通过为每条边附加一个单位权值，可以在求解最小割时优先选择边数较少的方案，从而同时解决两个问题。这种策略不仅简化了问题的求解过程，还确保了结果的最优性。 ... [详细]

蜡笔小新 2024-11-07 14:50:22
c语言
2012年9月12日优酷土豆校园招聘笔试题目解析与备考指南

2012年9月12日，优酷土豆校园招聘笔试题目解析与备考指南。在选择题部分，有一道题目涉及中国人的血型分布情况，具体为A型30%、B型20%、O型40%、AB型10%。若需确保在随机选取的样本中，至少有一人为B型血的概率不低于90%，则需要选取的最少人数是多少？该问题不仅考察了概率统计的基本知识，还要求考生具备一定的逻辑推理能力。 ... [详细]

蜡笔小新 2024-11-06 15:25:14
bit
每日精选Codeforces训练题：1119E（贪心算法）、821C（栈模拟）和645D（拓扑排序）

题目涉及三种不同类型的算法问题：1119E（贪心算法）、821C（栈模拟）和645D（拓扑排序）。其中，1119E的问题背景是有n种不同长度的棍子，长度分别为2^0, 2^1, …, 2^(n-1)，每种棍子的数量为a[i]。任务是计算可以组成的三角形数量。根据三角形的性质，任意两边之和必须大于第三边。该问题可以通过贪心算法高效解决，通过合理选择棍子组合来最大化三角形的数量。 ... [详细]

蜡笔小新 2024-11-03 11:42:58
sum
HDU 2176 石子游戏：多堆Nim博弈策略分析

在多堆石子游戏中，通过分析Nim博弈策略，探讨了如何在限定时间和内存条件下实现最优解。本文详细研究了石子游戏中的数学原理和算法优化方法，旨在为参与者提供有效的策略指导。具体而言，文章讨论了不同堆数下的Nim值计算及其应用，帮助玩家在复杂的博弈环境中取得优势。 ... [详细]

蜡笔小新 2024-11-02 10:46:31
sum
洛谷 P4035 [JSOI2008] 球形空间生成器（高斯消元法 / 模拟退火算法）

本文介绍了洛谷 P4035 [JSOI2008] 球形空间生成器问题的解决方案，主要使用了高斯消元法和模拟退火算法。通过这两种方法，可以高效地求解多维空间中的球心位置。文章提供了详细的算法模板和实现代码，适用于 ACM 竞赛和其他相关应用场景。数据范围限制在 10 以内，确保了算法的高效性和准确性。 ... [详细]

蜡笔小新 2024-11-08 13:55:00
bit
Linux 环境下多线程编程实战案例分析

在 Linux 环境下，多线程编程是实现高效并发处理的重要技术。本文通过具体的实战案例，详细分析了多线程编程的关键技术和常见问题。文章首先介绍了多线程的基本概念和创建方法，然后通过实例代码展示了如何使用 pthreads 库进行线程同步和通信。此外，还探讨了多线程程序中的性能优化技巧和调试方法，为开发者提供了宝贵的实践经验。 ... [详细]

蜡笔小新 2024-11-08 13:02:21
bit
佩尔方程的递推关系式：x² - dy² = 1 的深入解析

本文深入探讨了佩尔方程 \( x^2 - dy^2 = 1 \) 的递推关系式。通过构造特定的矩阵并利用矩阵快速幂的方法，可以高效地计算出该方程的第 k 组解。此外，文章还详细分析了递推关系式的数学背景及其在数论中的应用，为相关研究提供了坚实的理论基础。 ... [详细]

蜡笔小新 2024-11-08 11:28:27
bit
Prim算法优化实现：基于优先队列的最小生成树构建方法

Prim算法在处理稠密图时表现出色，尤其适用于边数远多于顶点数的情形。传统实现的时间复杂度为 \(O(n^2)\)，但通过引入优先队列进行优化，可以在点数为 \(m\)、边数为 \(n\) 的情况下显著降低时间复杂度，提高算法效率。这种优化方法不仅能够加速最小生成树的构建过程，还能在大规模数据集上保持良好的性能表现。 ... [详细]

蜡笔小新 2024-11-01 16:06:14
get
Java新手求助：如何优雅地向心仪女生索要QQ联系方式（附代码示例与技巧）

在端午节后的闲暇时光中，我无意间在技术社区里发现了一篇关于如何巧妙地向心仪女生索取QQ联系方式的文章，顿时感到精神焕发。这篇文章详细介绍了源自《啊哈！算法》的方法，不仅图文并茂，还提供了实用的代码示例和技巧，非常适合 Java 新手学习和参考。 ... [详细]

蜡笔小新 2024-10-30 13:45:35

淡水鱼yw灬s

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

Tags | 热门标签

RankList | 热门文章