【洛谷P4251】[SCOI2015]小凸玩矩阵(二分+二分图匹配)
2024-09-06 08:46:49
题意:
给出一个\(n*m\)的矩阵\(A\)。现要从中选出\(n\)个数,任意两个数不能在同一行或者同一列。
现在问选出的\(n\)个数中第\(k\)大的数的最小值是多少。
思路:
显然二分一下答案,然后找出所有不超过二分答案的边求最大匹配,判断一下是否小于\(n-k+1\)即可。
/*
* Author: heyuhhh
* Created Time: 2019/11/7 15:27:40
*/
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '\n'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '\n'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 255, M = 1e5 + 5;
int n, m, k;
int val[N][N];
struct Edge{
int v, next;
}e[M];
int head[N], tot;
void adde(int u, int v) {
e[tot].v = v; e[tot].next = head[u]; head[u] = tot++;
}
int T, vis[N];
int match[N];
int dfs(int u) {
for(int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if(vis[v] != T) {
vis[v] = T;
if(match[v] == -1 || dfs(match[v])) {
match[v] = u;
return 1;
}
}
}
return 0;
}
bool chk(int x) {
memset(head, -1, sizeof(head)); tot = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(val[i][j] <= x) adde(i, j);
}
}
memset(match, -1, sizeof(match));
int ans = 0;
for(int i = 1; i <= n; i++) {
++T; ans += dfs(i);
}
return ans >= n - k + 1;
}
void run(){
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> val[i][j];
}
}
int l = 1, r = INF, mid;
while(l < r) {
mid = (l + r) >> 1;
if(chk(mid)) r = mid;
else l = mid + 1;
}
cout << l << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
while(cin >> n >> m >> k) run();
return 0;
}
最新文章
- Oracle_多表查询
- Table样式
- jquery实现动画
- java实现顺序栈
- js 读写cookie。不同路径会储存各自的cookie。而 在v.net环境下读写是在 / 根目录。
- DOCTYPE与浏览器模式详解(标准模式&;混杂模式)
- Visual C++ 6.0常用快捷键
- 【剑指offer】数字数组中只出现一次(2)
- JMeter安装和简介
- Swagger文档添加file上传参数写法
- linux 消息队列
- echarts x轴 增加滚动条
- apache多站点vhost.conf配置
- py库: arrow (时间)
- 洛谷 P2672 推销员 解题报告
- hdu1846 Brave Game 博弈
- [转帖]";微信支付";勒索病毒制造者被锁定 传播、危害和疫情终极解密 --- 可以学习下一年火绒团队的分析原理的精神.
- (笔记)Linux下的解压、压缩命令集合
- 安装 wordpress 出现 抱歉,我不能写入wp-config.php文件
- poj 3414 Pots(广搜BFS+路径输出)
热门文章
- Linux系统学习 五、网络基础—网络通信协议
- Centos7下的zabbix安装与部署
- charles使用(安装、mock、限速、断点功能)
- UVA 12165 Triangle Hazard
- ajax成功请求到后台(进断点),但是浏览器控制台报404错误!
- 更新GitHub项目出现There is no tracking information for the current branch. Please specify which branch you want to merge with. 怎么解决
- Tomcat 设置JVM内存大小
- 基于SincNet的原始波形说话人识别
- js ajax设置和获取自定义header信息的方法总结
- linux下通过命令行把文件拷贝到U盘上