题目链接

思路:题目要求变相解答一下,求出是否有n-k个数,不大于当前求的第k个数

而每一行每一列只能有一个数,就可以得到一个二分图的思路,边上的权值就是第i行第j列这个数的值

对于答案就是第k大的数,则用二分来求

每一次对mid进行判断时,要重建图,以满足要求

#include <cstdio>
#include <iostream>
#include <cctype>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std; #define clr(x) memset(x,0,sizeof(x))
#define int long long inline int read(){
int s=;bool flag=true;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')flag=false;ch=getchar();}
while(isdigit(ch)){s=(s<<)+(s<<)+ch-'';ch=getchar();}
return flag?s:-s;
} inline void out_put(int x){
if(x<) putchar('-'),x=-x;
if(x>) out_put(x/);
putchar(x%+'');
} inline void print(int x){out_put(x),puts("");} const int N=;
const int inf=0x3f3f3f3f3f3f3f3f3f;
bool vis[N],line[N][N];
int row[N],w[N][N];
int n,m,k; inline bool find(int x){
for(int i=;i<=m;i++)
if(line[x][i] && !vis[i]){
vis[i]=true;
if(!row[i] || find(row[i])){
row[i]=x;
return true;
}
}
return false;
} inline void rebuild(int limit){
clr(line),clr(row);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(w[i][j]<=limit)
line[i][j]=true;
} inline bool check(int x){
rebuild(x);
int cnt=;
for(int i=;i<=n;i++){
clr(vis);
if(find(i)) cnt++;
}
if(cnt>n-k) return true;
return false;
} signed main(void){
n=read(),m=read(),k=read();
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
w[i][j]=read();
int l=,r=inf,ans;
while(l<=r){
int mid=(l+r)>>;
if(check(mid))r=mid-,ans=mid;
else l=mid+;
}
print(ans);
return ;
}

最新文章

  1. NOIp 1109
  2. leetcode 397
  3. shell编写mysql备份工具
  4. Ext JS4 学习笔记之发送表单(Form)时也将表单下的表格(Grid)数据一同发送的方法
  5. JAVA中ArrayList用法
  6. 关于ax+by=c的解x,y的min(|x|+|y|)值问题
  7. 转:Internal Sales Order (ISO) Process Flow
  8. 在Window IIS中安装运行node.js应用—你疯了吗
  9. 两种隐藏元素方式【display: none】和【visibility: hidden】的区别及由此引出的问题
  10. Spring注入静态变量(转)
  11. C++习题 对象转换
  12. 导入导出csv文件
  13. 2018 年 3 月 iOS 面试总结(上市公司,BAT)
  14. Elasticsearch java api 常用查询方法QueryBuilder构造举例
  15. Linux shell脚本中shift的用法说明
  16. Stateful Future Transformation
  17. Android简易项目--傻瓜式阿拉伯语输入法(Dummy Arabic Input)
  18. Azkaban学习之路 (二)Azkaban的安装
  19. HDU 3032 Nim or not Nim? (sg函数)
  20. Java - io输入输出流 --转换流

热门文章

  1. Spring5:面向切面
  2. Java 虚拟机中的运行时数据区分析
  3. Java IO 流 -- 设计模式:装饰设计模式
  4. PL/SQL 九九乘法表
  5. java中使用Semaphore构建阻塞对象池
  6. 后缀数组SA
  7. 徐州I
  8. 【思科】OSI和TCP/IP分层
  9. 7.JUC线程高级-生产消费问题&虚假唤醒
  10. 百度Openrasp开源的应用运行时自我保护产品,安装教程。