程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 4443: [Scoi2015]小禿玩矩陣|二分答案|匈牙利

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

編輯：C++入門知識

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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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<