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