[BZOJ4443][Scoi2015]小凸玩矩阵 二分答案+二分图最大匹配



事实上,第k大相当于第n-k+1小.
那么二分答案,找到最小的满足有至少n-k+1个数<=x的x.
为了check(mid),我们建一个二分图,将<=mid的点的横纵坐标之间连一条边,跑最大匹配即可.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1024
using namespace std;
int n,m,k,map[N][N];
int head[N],to[N*N],next[N*N],f[N*N],tot=1;
inline void add(int x,int y)
{
    to[++tot]=y;f[tot]=1;next[tot]=head[x];head[x]=tot;
    to[++tot]=x;f[tot]=0;next[tot]=head[y];head[y]=tot;
}
int s,t;
int dis[N],q[N],l=1,r;
bool bfs()
{
    l=1,r=0;
    memset(dis,-1,sizeof dis);
    q[++r]=s;dis[s]=0;
    int x,y;
    while(l<=r)
    {
        x=q[l++];
        for(int i=head[x];i;i=next[i])if(dis[y=to[i]]==-1&&f[i])
        {
            dis[y]=dis[x]+1;
            if(y==t)return 1;
            q[++r]=y;
        }
    }
    return 0;
}
int dinic(int x,int flow)
{
    if(x==t)return flow;
    int a,temp=flow;
    for(int i=head[x];i;i=next[i])if(dis[to[i]]==dis[x]+1&&f[i])
    {
        a=dinic(to[i],min(temp,f[i]));
        if(!a)dis[to[i]]=-1;
        temp-=a;f[i]-=a;f[i^1]+=a;
        if(!temp)return flow;
    }
    return flow-temp;
}
int maxflow()
{
    int re=0;
    while(bfs())re+=dinic(s,999999999);
    return re;
}
bool check(int mid)
{
    memset(head,0,sizeof head);
    memset(next,0,sizeof next);
    tot=1;
    s=0,t=n+m+1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)if(map[i][j]<=mid)add(i,j+n);
    }
    for(int i=1;i<=n;i++)add(s,i);
    for(int j=1;j<=m;j++)add(j+n,t);
    return maxflow()>=n-k+1;
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)scanf("%d",&map[i][j]);
    }
    int l=1,r=1000000007,mid,ans;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(check(mid))ans=r=mid;
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注