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

推荐阅读

main
JSOI2010 蔬菜庆典：树结构中的无限大权值问题

本文探讨了 JSOI2010 的蔬菜庆典问题，主要关注如何处理非根非叶子节点的无限大权值情况。通过分析根节点及其子树的特性，提出了有效的解决方案，并详细解释了算法的实现过程。 ... [详细]

蜡笔小新 2024-12-22 18:57:48
main
丽江客栈选择问题

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

蜡笔小新 2024-12-22 20:15:25
main
紫荆花之恋：动态树上的小精灵友谊问题

本题来自WC2014，题目编号为BZOJ3435、洛谷P3920和UOJ55。该问题描述了一棵不断生长的带权树及其节点上小精灵之间的友谊关系，要求实时计算每次新增节点后树上所有可能的朋友对数。 ... [详细]

蜡笔小新 2024-12-22 14:36:54
main
实现页面自动加载更多内容功能：类微博和Pinterest的设计

在现代Web应用中，当用户滚动到页面底部时，自动加载更多内容的功能变得越来越普遍。这种无刷新加载技术不仅提升了用户体验，还优化了页面性能。本文将探讨如何实现这一功能，并介绍一些实际应用案例。 ... [详细]

蜡笔小新 2024-12-23 17:01:04
main
字符串中特定字符的移除方法

本文介绍如何从字符串中移除大写、小写、特殊、数字和非数字字符，并提供了多种编程语言的实现示例。 ... [详细]

蜡笔小新 2024-12-22 00:08:06
main
病毒特征检测 - AC自动机应用

题目描述了一个病毒检测问题，要求使用AC自动机算法统计目标文本中多个模式串的出现次数。 ... [详细]

蜡笔小新 2024-12-14 17:53:50
main
在子模块目录中运行pre-commit遇到的问题及解决方案

本文探讨了在Git子模块目录中运行pre-commit时遇到的错误，并提供了一种通过Docker环境解决此问题的方法。 ... [详细]

蜡笔小新 2024-12-10 15:02:14
main
问题 F: Jack 的 A+B 数字格式化

问题F: Jack的A+B数字格式化时间限制: 1 秒内存限制: 128 MB 提交次数: 1996 解决次数: 601 [提交] [状态] [出题人: jsu_admin] ... [详细]

蜡笔小新 2024-12-09 07:43:02
main
NOIP 2018 提高组模拟赛 8.25 - 矩阵交集问题

本题涉及矩阵的交集计算，通过排序和权值线段树实现高效求解。 ... [详细]

蜡笔小新 2024-12-08 15:34:47
main
SCOI2013 day2 密码(password)

题目描述：首先看到这题应该知道该怎么裸吧…………以每个字符和间隙为中心可以建立若干个等和不等关系。相等关系可以用并查集合并，不等关系之间连边。然后对每一 ... [详细]

蜡笔小新 2024-12-08 15:10:51
buffer
HTTP请求与响应机制详解

本文深入探讨了HTTP请求和响应对象的使用，详细介绍了如何通过响应对象向客户端发送数据、处理中文乱码问题以及常见的HTTP状态码。此外，还涵盖了文件下载、请求重定向、请求转发等高级功能。 ... [详细]

蜡笔小新 2024-12-23 20:40:08
main
如何高效清空C++标准输入缓冲区

本文探讨了在C++中如何有效地清空输入缓冲区，确保程序只处理最近的输入并丢弃多余的输入。我们将介绍一种不阻塞的方法，并提供一个具体的实现方案。 ... [详细]

蜡笔小新 2024-12-23 15:44:01
main
在Xcode中配置自定义文本样式

本文探讨了如何在iOS开发环境中，特别是在Xcode 6.1中，设置和应用自定义文本样式。我们将详细介绍实现方法，并提供一些实用的技巧。 ... [详细]

蜡笔小新 2024-12-23 14:36:31
instance
JavaScript 基础语法指南

本文详细介绍了 JavaScript 的基础语法，包括变量、数据类型、运算符、语句和函数等内容，旨在为初学者提供全面的入门指导。 ... [详细]

蜡笔小新 2024-12-23 10:54:44
main
Alluxio 1.5.0 版本发布：增强功能与优化

Alluxio 1.5.0 开源版本引入了多项新特性和改进，旨在提升数据访问速度和系统互操作性。 ... [详细]

蜡笔小新 2024-12-10 10:47:59

淡水鱼yw灬s

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

Tags | 热门标签

RankList | 热门文章