【题解】
二分答案+二分图匹配。
先二分最小值Min，然后扫一遍这个矩阵，把满足a[i][j]<=Min的i,j连边，之后跑二分图匹配，如果最大匹配数大于等于n-k+1，当前的Min即是合法的。题目中要求选出的数不能在同一行或者同一列，而这种行与列连边跑二分图的做法就保证了一行与一列对应，最多只能选一次。题目中求第k大数的最小值，即有n-k+1个数小于等于Min，也就是最大匹配数大于等于n-k+1.
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define N 300 5 #define rg register 6 using namespace std; 7 int n,m,k,tmp,tot,T,last[N],a[N][N],p[N],v[N]; 8 struct edge{ 9 int to,pre; 10 }e[N*N]; 11 inline int read(){ 12 int k=0,f=1; char c=getchar(); 13 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 14 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 15 return k*f; 16 } 17 bool dfs(int x){ 18 for(rg int i=last[x],to;i;i=e[i].pre) if(v[to=e[i].to]!=T){ 19 v[to]=T; 20 if((!p[to])||dfs(p[to])){ 21 p[to]=x; return 1; 22 } 23 } 24 return 0; 25 } 26 inline bool check(int x){ 27 tmp=0; tot=0; T=0; 28 for(rg int i=1;i<=n;i++) last[i]=0; 29 for(rg int i=1;i<=m;i++) v[i]=0,p[i]=0; 30 for(rg int i=1;i<=n;i++) 31 for(rg int j=1;j<=m;j++) if(a[i][j]<=x){ 32 e[++tot]=(edge){j,last[i]}; last[i]=tot; 33 } 34 for(rg int i=1;i<=n;i++) ++T,tmp+=dfs(i); 35 return tmp>n-k; 36 } 37 int main(){ 38 n=read(); m=read() ;k=read(); 39 int l=2e9,r=0; 40 for(rg int i=1;i<=n;i++) 41 for(rg int j=1;j<=m;j++){ 42 a[i][j]=read(); 43 l=min(l,a[i][j]); 44 r=max(r,a[i][j]); 45 } 46 while(l+1<r){ 47 int mid=(l+r)>>1; 48 if(check(mid)) r=mid; else l=mid; 49 } 50 printf("%d ",r); 51 return 0; 52 }