【洛谷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
hdu 5439（找规律）的数列求和问题

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

蜡笔小新 2023-12-12 14:05:58
include
SPOJ2829 TLETime Limit Exceeded 题解及优化方法

本文介绍了SPOJ2829题目的解法及优化方法。题目要求找出满足一定条件的数列，并对结果取模。文章详细解释了解题思路和算法实现，并提出了使用FMT优化的方法。最后，对于第三个限制条件，作者给出了处理方法。文章最后给出了代码实现。 ... [详细]

蜡笔小新 2023-12-09 21:18:30
case
Open judge C16H: Magical Balls 快速幂+逆元问题解析

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

蜡笔小新 2023-12-14 12:03:27
main
P1651 塔 (动态规划) 的最大高度计算方法

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

蜡笔小新 2023-12-13 19:52:19
main
李逍遥寻找仙药的迷阵之旅

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

蜡笔小新 2023-12-12 13:59:33
main
Comet OJ - Contest #2 B　她的想法、他的战斗（概率　＋　数学）

题目描述Takuru是一名情报强者，所以他想利用他强大的情报搜集能力来当中间商赚差价。Takuru的计划是让Hinae帮他去市场上买一个商品，然后再以另一个价格卖掉它。Takur ... [详细]

蜡笔小新 2023-10-15 11:48:13
main
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
main
STL迭代器的种类及其功能介绍

本文介绍了标准模板库(STL)定义的五种迭代器的种类和功能。通过图表展示了这几种迭代器之间的关系，并详细描述了各个迭代器的功能和使用方法。其中，输入迭代器用于从容器中读取元素，输出迭代器用于向容器中写入元素，正向迭代器是输入迭代器和输出迭代器的组合。本文的目的是帮助读者更好地理解STL迭代器的使用方法和特点。 ... [详细]

蜡笔小新 2023-12-10 15:17:25
main
Codeforces Round #383 (Div. 2) D 分组背包

给出一群女孩的重量和颜值和她们的朋友关系现在有一个舞台ab是朋友bc是朋友ac就是朋友给出最大承重可以邀请这些女孩来玩对于每一个朋友团体全邀请or邀请一个or不邀请问能邀请的女孩的 ... [详细]

蜡笔小新 2023-10-17 17:22:42
format
APUE学习笔记可变参数（apue中错误输出函数的实现）

2019独角兽企业重金招聘Python工程师标准voiderr_dump(constchar*fmt,){va_listap;va_start(ap,fmt);初始化 ... [详细]

蜡笔小新 2023-10-16 10:06:39
main
[APIO2012]派遣解题报告

796.[APIO2012]派遣在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。在这个帮派里，有一名忍者被称之为Master。 ... [详细]

蜡笔小新 2023-10-15 20:32:49
perl
Android 新闻App的本地服务器搭建教程

本文介绍了在开发Android新闻App时，搭建本地服务器的步骤。通过使用XAMPP软件，可以一键式搭建起开发环境，包括Apache、MySQL、PHP、PERL。在本地服务器上新建数据库和表，并设置相应的属性。最后，给出了创建new表的SQL语句。这个教程适合初学者参考。 ... [详细]

蜡笔小新 2023-12-14 17:15:19
match
《数据结构》学习笔记3——串匹配算法性能评估

本文主要讨论串匹配算法的性能评估，包括模式匹配、字符种类数量、算法复杂度等内容。通过借助C++中的头文件和库，可以实现对串的匹配操作。其中蛮力算法的复杂度为O(m*n)，通过随机取出长度为m的子串作为模式P，在文本T中进行匹配，统计平均复杂度。对于成功和失败的匹配分别进行测试，分析其平均复杂度。详情请参考相关学习资源。 ... [详细]

蜡笔小新 2023-12-13 16:16:05
main
动态规划算法的基本步骤及最长递增子序列问题详解

本文详细介绍了动态规划算法的基本步骤，包括划分阶段、选择状态、决策和状态转移方程，并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中，在以后尽可能多地利用这些子问题的解，从而提高算法的效率。 ... [详细]

蜡笔小新 2023-12-13 15:38:19
main
[HDU5184] Brackets

前言很好的一道卡特兰数入门题，不板也不难题目HDU讲解括号匹配是经典的卡特兰数问题首先我们把无解与唯一解的情况特判出来，再考虑问题传统的卡特兰数的括号匹配对应的模型为从$(0,0) ... [详细]

蜡笔小新 2023-10-17 13:36:36

淡水鱼yw灬s

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

Tags | 热门标签

RankList | 热门文章