首页 > 代码库 > BZOJ 4443 小凸玩矩阵

BZOJ 4443 小凸玩矩阵

二分+网络流。

#include<iostream>#include<cstring>#include<cstdio>#include<queue>#include<algorithm>#define maxn 255#define maxv 10050#define maxe 500500#define inf 1000000007using namespace std;int n,m,k,g[maxv],nume=1,map[maxn][maxn],s,t;int dis[maxv];bool vis[maxv];queue <int> q; struct edge{    int v,f,nxt;}e[maxe];void addedge(int u,int v,int f){    e[++nume].v=v;e[nume].f=f;e[nume].nxt=g[u];g[u]=nume;    e[++nume].v=u;e[nume].f=0;e[nume].nxt=g[v];g[v]=nume;}bool bfs(){    while (!q.empty()) q.pop();    for (int i=s;i<=t;i++) {dis[i]=inf;vis[i]=false;}    dis[s]=0;vis[s]=true;q.push(s);    while (!q.empty())    {        int head=q.front();q.pop();        for (int i=g[head];i;i=e[i].nxt)        {            int v=e[i].v;            if ((!vis[v]) && (e[i].f))            {                vis[v]=true;dis[v]=dis[head]+1;                q.push(v);            }        }    }    if (!vis[t]) return false;    return true;}int dinic(int x,int low){    if (x==t) return low;    int ret=0;    for (int i=g[x];i && low;i=e[i].nxt)    {        int v=e[i].v;        if ((dis[v]==dis[x]+1) && (e[i].f))        {            int dd=dinic(v,min(low,e[i].f));            e[i].f-=dd;e[i^1].f+=dd;            low-=dd;ret+=dd;        }    }    if (!ret) dis[x]=inf;    return ret;}bool check(int x){    memset(g,0,sizeof(g));    nume=1;    for (int i=1;i<=n;i++) addedge(s,i,1);    for (int i=1;i<=m;i++) addedge(i+n,t,1);    for (int i=1;i<=n;i++)        for (int j=1;j<=m;j++)        {            if (map[i][j]<=x)                addedge(i,j+n,1);        }    int max_flow=0;    while (bfs())        max_flow+=dinic(s,inf);    if (max_flow<n-k+1) return false;    return true;}int half_search(){    int l=1,r=1000000000,ans;    while (l<=r)    {        int mid=l+r>>1;        if (check(mid)) {ans=mid;r=mid-1;}        else l=mid+1;    }    return ans;}int main(){    scanf("%d%d%d",&n,&m,&k);    s=0;t=n+m+1;    for (int i=1;i<=n;i++)        for (int j=1;j<=m;j++)            scanf("%d",&map[i][j]);    printf("%d\n",half_search());    return 0;}

 

BZOJ 4443 小凸玩矩阵