BZOJ 4443 [Scoi2015]小凸玩矩阵

题目大意

给你一个N*M的矩阵，选出N个数使得没有两个数在同一行/同一列，求第k大值的最小值。

这道题看了两分钟想到了二分+DFS，正解二分+二分图最大匹配，也还算可以吧。

本来计划二分一个第k大的值（答案），之后往里塞K-1个比它小的就可以了qwq

但是轻易地WA了（为什么能过样例呢┗|｀O′|┛）

可以换一种方法，倒着往里面加，加进去n-(k-1)个就可以了qwq

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,k,s[251][251],pr[501],maxn;
bool use[501];
bool xyl(int tx)
{
    for(int i=1;i<=m;++i)
        if(s[tx][i]<=maxn&&!use[i+n])
        {
            use[i+n]=true;
            if(!pr[i+n]||xyl(pr[i+n]))
            {
                pr[i+n]=tx;
                return true;
            }
        }
    return false;
}
bool check()
{
    memset(pr,0,sizeof pr);
    int cnt=0;
    for(int i=1;i<=n;++i)
    {
        memset(use,false,sizeof use);
        if(xyl(i)) ++cnt;
        if(cnt==n-k+1) return true;
    }
    return false;
}
int bisection()
{
    int l=0,r=1000000001;
    while(l<r)
    {
        maxn=(l+r)>>1;
        if(check()) r=maxn;
        else l=maxn+1;
    }
    return r;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%d",&s[i][j]);
    printf("%d\n",bisection());
}