题意

给出一个N*M（N<=M)的矩阵A,要求小秃从其中选出N个数，其中任意两个数字不能在同一行或同一列，求选出来的N个数中第K大的数字的最小值是多少。 1<=K<=N<=M<=250,1<=矩阵元素<=10^9

分析

一眼题。。。 把第k大变成第n-k+1小，二分答案，然后用网络流判断是否能在原图中找到k个点使得任意两点不在同一行同一列且都不大于二分值即可。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=255; const int inf=0x3f3f3f3f; int cnt,n,m,map[N][N],last[N*2],dis[N*2],cur[N*2],s,t,ans,k; struct edge{int to,c,next;}e[N*N*2]; queue <int> q; void addedge(int u,int v,int c) { e[++cnt].to=v;e[cnt].c=c;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].c=0;e[cnt].next=last[v];last[v]=cnt; } void build(int mid) { cnt=1;s=0;t=n+m+1; memset(last,0,sizeof(last)); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (map[i][j]<=mid) addedge(i,j+n,1); for (int i=1;i<=n;i++) addedge(s,i,1); for (int i=1;i<=m;i++) addedge(i+n,t,1); } bool bfs() { for (int i=s;i<=t;i++) dis[i]=0; dis[s]=1; while (!q.empty()) q.pop(); q.push(s); while (!q.empty()) { int u=q.front(); q.pop(); for (int i=last[u];i;i=e[i].next) if (e[i].c&&!dis[e[i].to]) { dis[e[i].to]=dis[u]+1; if (e[i].to==t) return 1; q.push(e[i].to); } } return 0; } int dfs(int x,int maxf) { if (x==t||!maxf) return maxf; int ret=0; for (int &i=cur[x];i;i=e[i].next) if (e[i].c&&dis[e[i].to]==dis[x]+1) { int f=dfs(e[i].to,min(e[i].c,maxf-ret)); e[i].c-=f; e[i^1].c+=f; ret+=f; if (maxf==ret) break; } return ret; } void dinic() { while (bfs()) { for (int i=s;i<=t;i++) cur[i]=last[i]; ans+=dfs(s,inf); } } int main() { scanf("%d%d%d",&n,&m,&k); int mx=0; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { scanf("%d",&map[i][j]); mx=max(mx,map[i][j]); } k=n-k+1; int l=1,r=mx; while (l<=r) { int mid=(l+r)/2; build(mid); ans=0; dinic(); if (ans>=k) r=mid-1; else l=mid+1; } printf("%d",r+1); return 0; }