给你一个n*m的网格,每个格子有一个数字,每行每列只能选一个数字,问所选数字中第k大的数字的最小值是多少
\(n \le 250\)
显然是二分图模型,但是有附加条件
初看十分不可做,主要原因是这个第k大
我们可以考虑二分一个答案,只对小于这个答案的格子建图
这样就转化成了一个判定性问题,根据每次的最大流与k的大小关系来判断
#include #include #include #include #include #include #include #include #include #include #define ls p<<1 #define rs p<<1|1 using namespace std; typedef long long ll; const int mxn=1e5+5,inf=1e9; int n,m,k,cnt; int S,T,ans,sum,a[555][555],hd[mxn],dep[mxn],cur[mxn]; inline int read() { char c=getchar(); int x=0,f=1; while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();} return x*f; } inline void chkmax(int &x,int y) {if(xy) x=y;} struct ed { int to,nxt,w; }t[mxn<<1]; inline void add(int u,int v,int w) { t[++cnt]=(ed) {v,hd[u],w}; hd[u]=cnt; t[++cnt]=(ed) {u,hd[v],0}; hd[v]=cnt; } int bfs() { queue q; q.push(S); memset(dep,0,sizeof(dep)); dep[S]=1; for(ll i=S;i<=T;++i) cur[i]=hd[i]; while(!q.empty()) { ll u=q.front(); q.pop(); for(ll i=hd[u];i!=-1;i=t[i].nxt) { ll v=t[i].to;// cout<0) dep[v]=dep[u]+1,q.push(v); } } return dep[T]; } int dfs(ll u,int f) { if(u==T) return f; for(int &i=cur[u];i!=-1;i=t[i].nxt) { ll v=t[i].to; if(dep[v]==dep[u]+1&&t[i].w>0) { int tp=dfs(v,min(t[i].w,f)); if(tp>0) { t[i].w-=tp; t[i^1].w+=tp; return tp; } } } return 0; } void Dinic() { while(bfs()) while(ll tp=dfs(S,inf)) ans+=tp; } int main() { n=read(); m=read(); k=read(); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) a[i][j]=read(); int l=1,r=inf; while(l>1; T=n+m+1; memset(hd,-1,sizeof(hd)); cnt=-1,ans=0; for(int i=1;i<=n;++i) add(S,i,1); for(int i=1;i<=m;++i) add(i+n,T,1); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { if(a[i][j]>mid) continue ; add(i,j+n,inf); } Dinic(); if(ans>=n-k+1) r=mid; else l=mid+1; } printf("%d",r); return 0; }