题面
https://www.luogu.org/problem/P4251
题解
// luogu-judger-enable-o2 #include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> #define ri register int #define N 300 using namespace std; int read() { int ret=0,f=0; char ch=getchar(); while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0' && ch<='9') ret=ret*10+(ch-'0'),ch=getchar(); return f?-ret:ret; } int n,m,k,tim,ans[N]; int va[N][N]; vector<int> to[N]; int vis[N],match[N]; bool dfs(int x) { for (ri i=0;i<to[x].size();i++) { int y=to[x][i]; if (vis[y]==tim) continue; vis[y]=tim; if (!match[y] || dfs(match[y])) { match[y]=x; return 1; } } return 0; } int check(int x) { for (ri i=1;i<=n;i++) to[i].clear(); memset(match,0,sizeof(match)); memset(vis,0,sizeof(vis)); for (ri i=1;i<=n;i++) for (ri j=1;j<=m;j++) if (va[i][j]<=x) to[i].push_back(j); tim=0; int cnt=0; for (ri i=1;i<=n;i++) { ++tim; if (dfs(i)) cnt++; } return cnt; } int main() { n=read(); m=read(); k=read(); k=n-k+1; for (ri i=1;i<=n;i++) for (ri j=1;j<=m;j++) va[i][j]=read(); int lb=0,rb=1e9; int ret=rb; while (lb<=rb) { int mid=(lb+rb)>>1; if (check(mid)>=k) ret=mid,rb=mid-1; else lb=mid+1; } printf("%d ",ret); return 0; }