小凸和小方是好朋友，小方给小凸一个N*M（N<=M)的矩阵A,要求小秃从其中选出N个数，其中任意两个数字不能在同一行或同一列，现小凸想知道选出来的N个数中第K大的数字的最小值是多少。

 

第一行给出三个整数N,M,K

接下来N行，每行M个数字，用来描述这个矩阵

 

如题 

 

 #include<iostream>

 #include<cstdlib>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<ctime>

 #include<algorithm>

 #include<iomanip>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<map>

 #include<set>

 #include<bitset>

 using namespace std;

 #define MAXN 1010

 #define MAXM 150010

 #define ll long long

 #define INF 1000000000

 #define MOD 1000000007

 #define eps 1e-8

 struct vec{

     int to;

     int fro;

     int v;

 };

 vec mp[MAXM];

 int tai[MAXN],cnt=;

 int q[MAXM],hd,tl;

 int s,t;

 int cur[MAXN];

 int d[MAXN];

 int ans;

 inline void be(int x,int y,int z){

     mp[++cnt].to=y;

     mp[cnt].fro=tai[x];

     tai[x]=cnt;

     mp[cnt].v=z;

 }

 inline void bse(int x,int y,int z){

     be(x,y,z);

     be(y,x,);

 }

 bool bfs(){

     int i,x,y;

     hd=tl=;

     q[tl++]=s;

     memset(d,,sizeof(d));

     d[s]=;

     while(hd!=tl){

         x=q[hd++];

         for(i=tai[x];i;i=mp[i].fro){

             y=mp[i].to;

             if(!d[y]&&mp[i].v){

                 d[y]=d[x]+;

                 q[tl++]=y;

             }

         }

     }

     return d[t];

 }

 int dfs(int x,int mx){

     if(x==t){

         return mx;

     }

     int y;

     ll re=,tmp;

     for(int &i=cur[x];i;i=mp[i].fro){

         y=mp[i].to;

         if(d[y]==d[x]+&&mp[i].v){

             tmp=dfs(y,min(mx,mp[i].v));

             re+=tmp;

             mx-=tmp;

             mp[i].v-=tmp;

             mp[i^].v+=tmp;

             if(!mx){

                 return re;

             }

         }

     }

     if(!re){

         d[x]=;

     }

     return re;

 }

 int n,m,a[][],k;

 bool OK(int x){

     int i,j;

     s=n+m+;

     t=s+;

     memset(tai,,sizeof(tai));

     cnt=;

     for(i=;i<=n;i++){

         for(j=;j<=m;j++){

             if(a[i][j]<=x){

                 bse(i,n+j,);

             }

         }

     }

     for(i=;i<=n;i++){

         bse(s,i,);

     }

     for(i=;i<=m;i++){

         bse(n+i,t,);

     }

     int flow=;

     while(bfs()){

         for(i=;i<=t;i++){

             cur[i]=tai[i];

         }

         flow+=dfs(s,INF);

     }

     return flow>=n-k+;

 }

 int main(){

     int i,j;

     scanf("%d%d%d",&n,&m,&k);

     for(i=;i<=n;i++){

         for(j=;j<=m;j++){

             scanf("%d",&a[i][j]);

         }

     }

     int l=,r=INF;

     int ans;

     while(l<=r){

         int mid=l+r>>;

         if(OK(mid)){

             ans=mid;

             r=mid-;

         }else{

             l=mid+;

         }

     }

     printf("%d\n",ans);

     return ;

 }

 /*

 */