二分+网络流。
#include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<algorithm> #define maxn 255 #define maxv 10050 #define maxe 500500 #define inf 1000000007 using namespace std; int n,m,k,g[maxv],nume=1,map[maxn][maxn],s,t; int dis[maxv]; bool vis[maxv]; queue <int> q; struct edge { int v,f,nxt; }e[maxe]; void addedge(int u,int v,int f) { e[++nume].v=v;e[nume].f=f;e[nume].nxt=g[u];g[u]=nume; e[++nume].v=u;e[nume].f=0;e[nume].nxt=g[v];g[v]=nume; } bool bfs() { while (!q.empty()) q.pop(); for (int i=s;i<=t;i++) {dis[i]=inf;vis[i]=false;} dis[s]=0;vis[s]=true;q.push(s); while (!q.empty()) { int head=q.front();q.pop(); for (int i=g[head];i;i=e[i].nxt) { int v=e[i].v; if ((!vis[v]) && (e[i].f)) { vis[v]=true;dis[v]=dis[head]+1; q.push(v); } } } if (!vis[t]) return false; return true; } int dinic(int x,int low) { if (x==t) return low; int ret=0; for (int i=g[x];i && low;i=e[i].nxt) { int v=e[i].v; if ((dis[v]==dis[x]+1) && (e[i].f)) { int dd=dinic(v,min(low,e[i].f)); e[i].f-=dd;e[i^1].f+=dd; low-=dd;ret+=dd; } } if (!ret) dis[x]=inf; return ret; } bool check(int x) { memset(g,0,sizeof(g)); nume=1; for (int i=1;i<=n;i++) addedge(s,i,1); for (int i=1;i<=m;i++) addedge(i+n,t,1); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { if (map[i][j]<=x) addedge(i,j+n,1); } int max_flow=0; while (bfs()) max_flow+=dinic(s,inf); if (max_flow<n-k+1) return false; return true; } int half_search() { int l=1,r=1000000000,ans; while (l<=r) { int mid=l+r>>1; if (check(mid)) {ans=mid;r=mid-1;} else l=mid+1; } return ans; } int main() { scanf("%d%d%d",&n,&m,&k); s=0;t=n+m+1; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&map[i][j]); printf("%d ",half_search()); return 0; }