【BZOJ4443】小凸玩矩阵（二分答案，二分图匹配）

题面

Description

小凸和小方是好朋友，小方给小凸一个N*M（N<=M)的矩阵A,要求小秃从其中选出N个数，其中任意两个数字不能在同一行或同一列，现小凸想知道选出来的N个数中第K大的数字的最小值是多少。

Input

第一行给出三个整数N,M,K

接下来N行，每行M个数字，用来描述这个矩阵

Output

如题

Sample Input

3 4 2

1 5 6 6

8 3 4 3

6 8 6 3

Sample Output

HINT

1<=K<=N<=M<=250,1<=矩阵元素<=10^9

题解

看到这种第\(K\)大都直接二分

二分答案，然后因为行列都只能选一个，很明显的二分图匹配。

拆点之后把权值小于二分值的格子连边，直接二分图匹配就行了。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;#define ll long long#define RG register#define MAX 500inline int read(){ RG int x=0,t=1;RG char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*t;}int n,m,g[MAX][MAX],K;struct Line{int v,next;}e[MAX*MAX];int h[MAX],cnt=1;inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}void Build(int Mid){ memset(h,0,sizeof(h));cnt=1; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(g[i][j]<=Mid)Add(i,j);}int match[MAX],vis[MAX],tot;bool dfs(int u){ for(int i=h[u];i;i=e[i].next) { int v=e[i].v; if(vis[v]==tot)continue; vis[v]=tot; if(!match[v]||dfs(match[v])){match[v]=u;return true;} } return false;}int check(){ memset(match,0,sizeof(match)); int ret=0; for(int i=1;i<=n;++i) { ++tot; if(dfs(i))++ret; } return ret;}int main(){ n=read();m=read();K=n-read()+1; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)g[i][j]=read(); int l=0,r=1e9,ans=1e9; while(l<=r) { int mid=(l+r)>>1; Build(mid); if(check()>=K)ans=mid,r=mid-1; else l=mid+1; } printf("%d\n",ans); return 0;}