bzoj 4443: [Scoi2015]小凸玩矩阵

.

题意：这么短自己看吧
题解：二分+二分图匹配
要求选出来的任意两个不在同一行或同一列，那就是把行和列连边跑二分图匹配。二分答案，看看能不能配到n-k+1个。
代码：

#include<cstdio>
#include<cstring>

int n,m,k,num=0,fst[260],a[260][260],t=0,v[260],mch[260];
struct edge
{
    int x,y,n;
}e[62510];

void ins(int x,int y)
{
    e[++num]={x,y,fst[x]};
    fst[x]=num;
}
bool fd(int x)
{
    for(int i=fst[x];i;i=e[i].n)
    {
        int y=e[i].y;
        if(v[y]!=t)
        {
            v[y]=t;
            if(!mch[y]||fd(mch[y]))
            {
                mch[y]=x;
                return 1;
            }
        }
    }
    return 0;
}
int chk(int x)
{
    memset(fst,0,sizeof(fst));
    num=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    if(a[i][j]<=x)
    ins(i,j);
    int ans=0;
    memset(mch,0,sizeof(mch));
    for(int i=1;i<=n;i++)
    {
        t++;
        ans+=fd(i);
    }
//  printf("%d %d\n",x,ans);
    return ans;
}
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",&a[i][j]);
    int l=1,len=1000000000;
    while(len)
    {
        int md=l+(len>>1);
        if(chk(md)<=n-k)
        {
            l=md+1;
            len=len-(len>>1)-1;
        }
        else
        len>>=1;
    }
    printf("%d",l);
}