【洛谷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

推荐阅读

string
贪心与优先队列：最小化加法代价问题

本题要求在一组数中反复取出两个数相加，并将结果放回数组中，最终求出最小的总加法代价。这是一个经典的哈夫曼编码问题，利用贪心算法可以有效地解决。 ... [详细]

蜡笔小新 2024-12-20 23:20:38
list
CUGB图论专题：排水系统中的最大流问题 - EK与Dinic算法解析

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

蜡笔小新 2024-12-25 17:47:23
list
Splay Tree 区间操作优化

本文详细介绍了使用Splay Tree进行区间操作的实现方法，包括插入、删除、修改、翻转和求和等操作。通过这些操作，可以高效地处理动态序列问题，并且代码实现具有一定的挑战性，有助于编程能力的提升。 ... [详细]

蜡笔小新 2024-12-26 18:47:12
string
2016年10月25日数学考试：斐波那契数列与矩阵快速幂的应用

本次考试于2016年10月25日上午7:50至11:15举行，主要涉及数学专题，特别是斐波那契数列的性质及其在编程中的应用。本文将详细解析考试中的题目，并提供解题思路和代码实现。 ... [详细]

蜡笔小新 2024-12-25 13:08:21
string
图论问题解析：POJ2762 从u到v或从v到u的可达性判断（强连通分量缩点与单向连通性检测）

本文深入探讨了POJ2762问题，旨在通过强连通分量缩点和单向连通性的判断方法，解决有向图中任意两点之间的可达性问题。文章详细介绍了算法原理、实现步骤，并附带完整的代码示例。 ... [详细]

蜡笔小新 2024-12-24 10:44:24
string
丽江客栈选择问题

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

蜡笔小新 2024-12-22 20:15:25
string
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]

蜡笔小新 2024-12-26 20:04:36
string
Weight the Tree（树形dp）

题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅！－－－－－&# ... [详细]

蜡笔小新 2024-12-26 15:55:56
string
洛谷 P4116 树上操作：颜色变换与路径查询

本题涉及一棵由N个节点组成的树（共有N-1条边），初始时所有节点均为白色。题目要求处理两种操作：一是改变某个节点的颜色（从白变黑或从黑变白）；二是查询从根节点到指定节点路径上的第一个黑色节点，若无则输出-1。 ... [详细]

蜡笔小新 2024-12-26 10:22:20
string
POJ 1691 矩形涂色问题 (DFS/状态压缩DP)

本题通过将每个矩形视为一个节点，根据其相对位置构建拓扑图，并利用深度优先搜索（DFS）或状态压缩动态规划（DP）求解最小涂色次数。本文详细解析了该问题的建模思路与算法实现。 ... [详细]

蜡笔小新 2024-12-25 18:27:21
list
360SRC安全应急响应：从漏洞提交到修复的全过程

本文详细介绍了360SRC平台处理一起关键安全事件的过程，涵盖从漏洞提交、验证、排查到最终修复的各个环节。通过这一案例，展示了360在安全应急响应方面的专业能力和严谨态度。 ... [详细]

蜡笔小新 2024-12-27 11:10:05
merge
Tetris 排名系统 (拓扑排序与并查集的应用)

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

蜡笔小新 2024-12-24 21:03:51
string
递推算法与大数处理

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

蜡笔小新 2024-12-23 12:18:55
text
C# XNA 中实现自定义 3x3 矩阵类：MMatrix33

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

蜡笔小新 2024-12-21 17:27:57
text
Linux环境下进程间通信：深入解析信号机制

本文详细探讨了Linux系统中信号的生命周期，从信号生成到处理函数执行完毕的全过程，并介绍了信号编程中的注意事项和常见应用实例。通过分析信号在进程中的注册、注销及处理过程，帮助读者理解如何高效利用信号进行进程间通信。 ... [详细]

蜡笔小新 2024-12-21 10:29:05

淡水鱼yw灬s

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

Tags | 热门标签

RankList | 热门文章