给定一个n*m的矩阵,现在要从矩阵中选择出n个元素,要求选出的元素不同行,不同列.现求选出的元素中第K大元素的最小值是多少.

链接

LOJ2006

BZOJ4443

题解

经典的二分图模型.很长时间不打网络流快忘了都.

首先题目要求最小值,显然这个答案是单调的,所以可以二分答案.然后构建一个二分图,左边为行,右边为列.当a[i,j]大于等于枚举的答案时,连接一条从左边第i个点到右边第j个点的边,流量为1.原点向左边的点连边,右边的点向汇点连边,流量均为1.然后跑网络流,判断最大流是否满足要求即可.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 100010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,m,i,j,k,lsum=1,cnt,low,high,mid,Ans,Found,al,flow;
int a[550][550];
int gap[N],gaps[N],head[N];

struct Flow{
    int t,next,fl,re;
}e[N*8];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline void Add(int s,int t,int fl){
    e[lsum].t=t;    e[lsum].fl=fl;  e[lsum].next=head[s];   e[lsum].re=lsum+1;  head[s]=lsum++;
    e[lsum].t=s;    e[lsum].fl=0;   e[lsum].next=head[t];   e[lsum].re=lsum-1;  head[t]=lsum++;
}

inline void Sap(int x){
    int F=al,mingap=cnt-1,i=0;
    if (x==cnt) {Found=1;   flow+=al;   return;}
    for (i=head[x];i;i=e[i].next)
        if (e[i].fl){
            if (gap[x]==gap[e[i].t]+1){
                al=Min(al,e[i].fl);
                Sap(e[i].t);
                if (gap[1]>=cnt)    return;
                if (Found)  break;
                al=F;
            }
            mingap=Min(mingap,gap[e[i].t]);
        }
    if (!Found){
        gaps[gap[x]]--; if (!gaps[gap[x]])  gap[1]=cnt;
        gaps[gap[x]=mingap+1]++;
    }   else e[i].fl-=al,e[e[i].re].fl+=al;
}

inline void MakeMap(int x){
    int i=0,j=0;
    memset(gap,0,sizeof(gap));  memset(gaps,0,sizeof(gaps));
    memset(head,0,sizeof(head));    memset(e,0,sizeof(e));
    cnt=flow=0; lsum=1;
    cnt=2+n+m;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (a[i][j]<=x) Add(1+i,1+n+j,1);
    for (i=1;i<=n;i++)  Add(1,1+i,1);
    for (i=1;i<=m;i++)  Add(1+n+i,cnt,1);
}

inline bool Check(int x){
    int i=0,j=0;
    MakeMap(x);
    gaps[0]=cnt;
    while (gap[1]<cnt){
        al=INF; Found=0;    Sap(1);
    }
    return (flow<n-k+1)?true:false;
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    low=1;  high=INF;   Ans=-1;
    while (low<=high){
        mid=(low+high)>>1;
        if (Check(mid)) low=mid+1;
        else Ans=mid,high=mid-1;
    }
    printf("%d\n",Ans);
    Check(Ans);
    return 0;
}