BZOJ2406矩阵

题目描述

题解

最大值最小，一眼二分没的说。

然后考虑建出这么个图，每行看做一个点，每列看做一个点，每个点看做一条连接行与列的边，源点向每行连s-mid__s+mid的边，行与列连L__R的边，列到汇连s-mid__s+mid的边。

然后判断是否有有源汇可行流。

建图时要让边权先减去下界！

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define N 209

#define NN 409

#define inf 2e9

using namespace std;

queue<int>q;

int tot,head[NN],a[N][N],deep[NN],cur[NN],si[N],sj[N],L,R,n,m,du[NN],ans;

inline int rd(){

    int x=;char c=getchar();bool f=;

    while(!isdigit(c)){if(c=='-')f=;c=getchar();}

    while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}

    return f?-x:x;

}

struct edge{int n,to,l;}e[NN*NN*];

inline void add(int u,int v,int l){

    e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l;

    e[++tot].n=head[v];e[tot].to=u;head[v]=tot;e[tot].l=;

}

inline bool bfs(int s,int t){

    memset(deep,,sizeof(deep));

    memcpy(cur,head,sizeof(head));

    q.push(s);deep[s]=;

    while(!q.empty()){

        int u=q.front();q.pop();

        for(int i=head[u];i;i=e[i].n){

            int v=e[i].to;

            if(!deep[v]&&e[i].l){deep[v]=deep[u]+;q.push(v);}

        }

    }

    return deep[t];

}

int dfs(int u,int t,int l){

    if(u==t||!l)return l;

    int flow=,f;

    for(int &i=cur[u];i;i=e[i].n){

        int v=e[i].to;

        if(deep[v]==deep[u]+&&(f=dfs(v,t,min(l,e[i].l)))){

            e[i].l-=f;e[i^].l+=f;l-=f;flow+=f;

            if(!l)break;

        }

    }

    return flow;

}

inline bool check(int mid){

    int s=,t=n+m+,ss=m+n+,tt=n+m+;

    memset(head,,sizeof(head));tot=;

    memset(du,,sizeof(du));

    for(int i=;i<=n;++i){

        int mi=max(,si[i]-mid);

        du[s]-=mi;du[i]+=mi;add(s,i,si[i]+mid-mi);

    }

    for(int i=;i<=m;++i){

        int mi=max(,sj[i]-mid);

        du[n+i]-=mi;du[t]+=mi;add(i+n,t,sj[i]+mid-mi);

    }

    for(int i=;i<=n;++i)

      for(int j=;j<=m;++j){du[i]-=L;du[n+j]+=L;add(i,n+j,R-L);}

    add(t,s,inf);

    for(int i=s;i<=t;++i){

        if(du[i]<)add(i,tt,-du[i]);

        else add(ss,i,du[i]);

    }

    while(bfs(ss,tt))dfs(ss,tt,inf);

    for(int i=head[ss];i;i=e[i].n)if(e[i].l)return ;

    for(int i=head[tt];i;i=e[i].n)if(e[i^].l)return ;

    return ;

}

int main(){

    n=rd();m=rd();

    for(int i=;i<=n;++i)for(int j=;j<=m;++j)a[i][j]=rd(),si[i]+=a[i][j],sj[j]+=a[i][j];

    L=rd();R=rd();

    int l=,r=;

    while(l<=r){

        int mid=(l+r)>>;

        if(check(mid))ans=mid,r=mid-;else l=mid+;

    }

    cout<<ans;

    return ;

}