Description
小凸和小方是好朋友，小方给小凸一个 (N imes M)（ (N leq M) )的矩阵 (A) ,要求小秃从其中选出 (N) 个数，其中任意两个数字不能在同一行或同一列，现小凸想知道选出来的 (N) 个数中第 (K) 大的数字的最小值是多少。
Input
第一行给出三个整数 (N) , (M) , (K)
接下来 (N) 行，每行 (M) 个数字，用来描述这个矩阵
Output
如题
Sample Input
3 4 2
1 5 6 6
8 3 4 3
6 8 6 3
Sample Output
3
HINT
(1 leq K leq N leq M leq 250) , (1 leq 矩阵元素 leq 10^9)
想法
题中的“小秃” 怕不是再说我呜呜
看到 第 (k) 大最小，下意识想到二分。
可二分需要满足有单调性啊？这道题中第 (k) 大的数肯定不是越大越满足条件的，满足条件的应是一段区间。
但我们仍可二分这个值的下限 (x) ，要满足从 (leq x) 的元素中可选出 (n-k+1) 个合法的。
怎么判断能不能选出 (n-k+1) 个合法的呢？
我一开始竟一直想怎么数据结构搞…
后来才意识到，“任两个不能在同一行或同一列” 是个挺经典的模型：把行和列当成点，将可选的元素所在的行与列连边，跑二分图匹配就好了。
这样我们得到下限 (x) 了，但仍有一个问题，能不能选出 (k-1) 个 (geq x) 的元素构成一个合法方案呢？
好巧的是，一定可以。
简略证明如下：
既然 (x) 是下限，那么在 (leq x-1) 的元素中一定选不出 (n-k+1) 个构成合法方案
那么在当前选了 (n-k+1) 个元素后再随便选 (k-1) 个元素构成合法方案，这 (n) 个元素中 (leq x-1) 的 (<n-k+1)
也就是说 (geq x) 的至少有 (k) 个。
那么，在我们选出的元素中，二分保证了 (leq x) 的至少有 (n-k+1) 个，上面的证明保证 (geq x) 的至少有 (k) 个，则第 (k) 大的一定是 (x)
这个证明太神了……我自己绝对想不到啊 (qwq)
要在考场上只能凭感觉猜了 (qwq)
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x;
}
const int N = 255;
int n,m,k;
int a[N][N];
int mp[N][N],vis[N],con[N];
bool find(int u){
for(int v=1;v<=m;v++){
if(!mp[u][v] || vis[v]) continue;
vis[v]=1;
if(!con[v] || find(con[v])){
con[v]=u;
return true;
}
}
return false;
}
bool check(int x){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
mp[i][j]=(a[i][j]<=x);
memset(con,0,sizeof(con));
int f=0;
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(find(i)) f++;
}
return f>=n-k+1;
}
int main()
{
n=read(); m=read(); k=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) a[i][j]=read();
int l=1000000009,r=0,mid;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
l=min(l,a[i][j]);
r=max(r,a[i][j]);
}
while(l<r){
mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d
",l);
return 0;
}