洛谷4251 [SCOI2015]小凸玩矩阵

Luogu

BZOJ

分析

二分答案+二分图匹配。

第 $k$ 大似乎并不好搞,于是考虑二分答案 $mid$ 。

考虑怎么 $\mathrm{check}$ 。

对于每个 $\leq mid$ 的元素,行向列连边。然后如果最大匹配 $\geq n-k+1$ ,就可行。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500+10;
const int M=130000+10;

int n,m,k;
int a[N][N];

struct Edge { int v,nxt; } e[M];
int head[M],cnt;

inline void addEdge(int u,int v) {
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

int vis[N],lnk[N];

inline int Hungary(int u) {
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (vis[v]) continue;
        vis[v]=1;
        if (!lnk[v]||Hungary(lnk[v])) return lnk[v]=u;
    }
    return 0;
}

inline int calc(int mid) {
    fill(head+1,head+n*m+1,0),cnt=0;
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=m;++j)
            if (a[i][j]<=mid) addEdge(i,j+n);
    memset(lnk,0,sizeof(lnk)); int s=0;
    for (re int i=1;i<=n;++i) {
        memset(vis,0,sizeof(vis));
        if (Hungary(i)) ++s;
    }
    return s;
}

int main() {
    n=read(),m=read(),k=read();
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=m;++j)
            a[i][j]=read();
    int L=1,R=1e9;
    while (L<R) {
        int mid=(L+R)>>1;
        if (calc(mid)>=n-k+1) R=mid;
        else L=mid+1;
    }
    printf("%d\n",L);
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 39 PM

发表评论