（上不了p站我要死了，侵权度娘背锅）

Description

小凸和小方是好朋友，小方给小凸一个N*M（N<=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<=K<=N<=M<=250,1<=矩阵元素<=10^9

首先，看到方格图，以及“不能在同一行或同一列”。就可以想到 行与列 是一个数的两个属性，而这两个属性不能有相同的。

二分图的最大匹配可以用来求解这一类的问题，即 选取最多的属性不相同的物品。

话虽如此，但这道题要求“第k大的数字最小”。也就是说选一个值x，可以找到n-k+1个属性不同的物品的值满足小于等于x的（包括自己嘛）。

为什么不能直接二分寻找大于x的匹配呢？因为我们要求的是最小值，而直接找第k大会找到满足条件的最大值。

#include
     
      #include
      
       #include
       
        using namespace std;template 
        
         inline void read(T &res){    T k=1,x=0;char ch=0;    while(ch<'0'||ch>'9'){
    if(ch=='-')k=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    res=x*k;}const int N=260;int n,m,k,c[N][N],maxn=0;int bl[N];bool vis[N];bool find(int x,int lim){    for(int i=1;i<=m;i++){        if((!vis[i])&&c[x][i]<=lim){            vis[i]=1;            if(bl[i]==0||find(bl[i],lim)){                bl[i]=x;                return true;            }        }    }    return false;}int ck(int x){    int cnt=0;    memset(bl,0,sizeof(bl));    for(int i=1;i<=n;i++){        memset(vis,0,sizeof(vis));        if(find(i,x)) cnt++;    }    return cnt;}int erfen(){    int le=1,ri=maxn;    while(le
         
          >1;        if(ck(mid)>=n-k+1) ri=mid;        else le=mid+1;    }    return le;}int main(){    read(n),read(m),read(k);    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++) read(c[i][j]),maxn=max(maxn,c[i][j]);    printf("%d\n",erfen());    return 0;}