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

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

阅读量：5923 次

发布时间：2019-06-19

本文共 1331 字，大约阅读时间需要 4 分钟。

第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 1000001using 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<