4443: [Scoi2015]小秃玩矩阵|二分答案|匈牙利

第K大看成第K小各种WA。

。。

第K大也就是第n−K+1小。所以就能够愉快的二分答案了

二分答案找出比当前答案小的数的位置的坐标。推断一下能否够选出满足不在同一行同一列的n−K+1个数，然后就能够愉快的跑匈牙利了，对于一个坐标(x,y)假设满足a[x][y]≤当前答案。就把第x行向第y列连边，然后跑匈牙利推断最大匹配是否大于n−K+1

匈牙利真是跑的飞快，然后就卡成rank1 QAQ

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<vector>

#include<cmath>

#include<queue>

#include<set>

#include<map>

#define ll long long

#define N 1000001

using namespace std;

int sc()

{

    int i=0,f=1; char c=getchar();

    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar();

    return i*f;

}

int a[255][255];

int head[N],nxt[N],lst[N],tim[N],from[N];

int n,m,tot,mx,TI,K;

void insert(int x,int y)

{

    lst[++tot]=y;nxt[tot]=head[x];head[x]=tot;

}

bool Hungary(int x)

{

    for(int i=head[x];i;i=nxt[i])

        if(tim[lst[i]]!=TI)

        {

            tim[lst[i]]=TI;

            if(!from[lst[i]]||Hungary(from[lst[i]]))

            {

                from[lst[i]]=x;

                return 1;

            }

        }

    return 0;

}

bool jud(int x)

{

    int ans=0;tot=0;

    for(int i=1;i<=n;i++)head[i]=0;

    for(int i=1;i<=m;i++)from[i]=0;

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

            if(a[i][j]<=x) insert(i,j);

    for(int i=1;i<=n;i++)

        TI++,ans+=Hungary(i);

    return ans>=K;

}

int main()

{

    n=sc();m=sc(),K=sc();K=n-K+1;

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

            mx=max(mx,a[i][j]=sc());

    int l=1,r=mx;

    while(l!=r)

    {

        int mid=l+r>>1;

        if(jud(mid))r=mid;

        else l=mid+1;

    }

    cout<<l;

    return 0;

}