[bzoj4443] [loj2006] [洛谷P4251] [Scoi2015]小凸玩矩阵

Description

小凸和小方是好朋友，小方给小凸一个 \(N \times M\)（ \(N \leq 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

3

HINT

\(1 \leq K \leq N \leq M \leq 250\) , \(1 \leq 矩阵元素 \leq 10^9\)

想法

题中的“小秃” 怕不是再说我呜呜

看到 第 \(k\) 大最小，下意识想到二分。
可二分需要满足有单调性啊？这道题中第 \(k\) 大的数肯定不是越大越满足条件的，满足条件的应是一段区间。
但我们仍可二分这个值的下限 \(x\) ，要满足从 \(\leq x\) 的元素中可选出 \(n-k+1\) 个合法的。

怎么判断能不能选出 \(n-k+1\) 个合法的呢？
我一开始竟一直想怎么数据结构搞…
后来才意识到，“任两个不能在同一行或同一列” 是个挺经典的模型：把行和列当成点，将可选的元素所在的行与列连边，跑二分图匹配就好了。

这样我们得到下限 \(x\) 了，但仍有一个问题，能不能选出 \(k-1\) 个 \(\geq x\) 的元素构成一个合法方案呢？
好巧的是，一定可以。
简略证明如下：
既然 \(x\) 是下限，那么在 \(\leq x-1\) 的元素中一定选不出 \(n-k+1\) 个构成合法方案
那么在当前选了 \(n-k+1\) 个元素后再随便选 \(k-1\) 个元素构成合法方案，这 \(n\) 个元素中 \(\leq x-1\) 的 \(<n-k+1\)
也就是说 \(\geq x\) 的至少有 \(k\) 个。
那么，在我们选出的元素中，二分保证了 \(\leq x\) 的至少有 \(n-k+1\) 个，上面的证明保证 \(\geq x\) 的至少有 \(k\) 个，则第 \(k\) 大的一定是 \(x\)

这个证明太神了……我自己绝对想不到啊 \(qwq\)
要在考场上只能凭感觉猜了 \(qwq\)

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

int read(){
    int x=0;
    char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x;
}

const int N = 255;

int n,m,k;
int a[N][N];

int mp[N][N],vis[N],con[N];
bool find(int u){
    for(int v=1;v<=m;v++){
        if(!mp[u][v] || vis[v]) continue;
        vis[v]=1;
        if(!con[v] || find(con[v])){
            con[v]=u;
            return true;
        }
    }
    return false;
}
bool check(int x){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            mp[i][j]=(a[i][j]<=x);
    memset(con,0,sizeof(con));
    int f=0;
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(find(i)) f++;
    }
    return f>=n-k+1;
}

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=1000000009,r=0,mid;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            l=min(l,a[i][j]);
            r=max(r,a[i][j]);
        }
    while(l<r){
        mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%d\n",l);
    
    return 0;
}

[bzoj4443] [loj2006] [洛谷P4251] [Scoi2015]小凸玩矩阵

原文：https://www.cnblogs.com/lindalee/p/11397182.html