首页 > 代码库 > 4443: [Scoi2015]小秃玩矩阵|二分答案|匈牙利

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

K<script type="math/tex" id="MathJax-Element-1">K</script>大看成第K<script type="math/tex" id="MathJax-Element-2">K</script>小各种WA。

。。


K<script type="math/tex" id="MathJax-Element-3">K</script>大也就是第n?K+1<script type="math/tex" id="MathJax-Element-4">n-K+1</script>小。所以就能够愉快的二分答案了
二分答案找出比当前答案小的数的位置的坐标。推断一下能否够选出满足不在同一行同一列的n?K+1<script type="math/tex" id="MathJax-Element-5">n-K+1</script>个数,然后就能够愉快的跑匈牙利了,对于一个坐标(x,y)<script type="math/tex" id="MathJax-Element-6">(x,y)</script>假设满足a[x][y]<script type="math/tex" id="MathJax-Element-7">a[x][y]\leq</script>当前答案。就把第x<script type="math/tex" id="MathJax-Element-8">x</script>行向第y<script type="math/tex" id="MathJax-Element-9">y</script>列连边,然后跑匈牙利推断最大匹配是否大于n?K+1<script type="math/tex" id="MathJax-Element-10">n-K+1</script>
匈牙利真是跑的飞快,然后就卡成rank1<script type="math/tex" id="MathJax-Element-11">rank1</script> 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;
}
<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

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