欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[上下界网络流] BZOJ2406: 矩阵

程序员文章站 2022-06-10 14:43:59
...

题意

[上下界网络流] BZOJ2406: 矩阵

题解

求最小值的最大值,容易想到二分答案。
对于当前二分的mid,现在就要考虑怎么验证,实际上就是要满足形如:Asum[i]Bsum[j]mid 的所有不等式都成立。
变形一下可以得到:Asum[i]midBsumAsum[i]+mid
这样就可以转换成有上下界的网络流问题了。
对每行/列建一个点。
S–>行i,流量[Asum1[i]mid,Asum1[i]+mid]
列j–>T,流量[Asum2[j]mid,Asum2[j]+mid]
行i–>列j,流量[L,R]
判断是否有可行流即可。

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1005,maxe=200005;
struct Edge{
    int from,to,flow,cap;
    Edge(int t1=0,int t2=0,int t3=0,int t4=0){ from=t1; to=t2; flow=t3; cap=t4; }
} Es[maxe];
int fir[maxn],nxt[maxe],tot=1;
void add(int x,int y,int z){
    Es[++tot]=Edge(x,y,0,z); nxt[tot]=fir[x]; fir[x]=tot;
    Es[++tot]=Edge(y,x,0,0); nxt[tot]=fir[y]; fir[y]=tot;
}
queue <int> que;
int S,T,SS,TT,N,d[maxn],tmp[maxn];
int n,m,ans,sum1[205],sum2[205],numL,numR;
bool Bfs(int S,int T){
    memset(d,63,sizeof(d)); int INF=d[0];
    while(!que.empty()) que.pop(); 
    que.push(S); d[S]=0; 
    while(!que.empty()){
        int x=que.front(); que.pop();
        for(int j=fir[x];j;j=nxt[j]) if(d[Es[j].to]==INF&&Es[j].cap>Es[j].flow){
            d[Es[j].to]=d[x]+1; que.push(Es[j].to);
        }
    }
    return d[T]!=INF;
}
int pos[maxn];
int find_Dfs(int x,int flow,int T){
    if(x==T||flow==0) return flow;
    int res=0,t;
    for(int &j=pos[x];j;j=nxt[j]){
        if(d[x]+1==d[Es[j].to]&&(t=find_Dfs(Es[j].to,min(flow,Es[j].cap-Es[j].flow),T))>0){
            Es[j].flow+=t; Es[j^1].flow-=t; 
            res+=t; flow-=t; if(flow==0) break;
        }
    }
    return res;
}
int Dinic(int S,int T){
    int MaxFlow=0;
    while(Bfs(S,T)){
        for(int i=1;i<=N;i++) pos[i]=fir[i]; 
        MaxFlow+=find_Dfs(S,1e+9,T);
    }
    return MaxFlow;
}
bool check(int mid){
    N=n+m; S=++N; T=++N; SS=++N,TT=++N;
    memset(fir,0,sizeof fir); tot=1;
    memset(tmp,0,sizeof tmp);
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++) add(i,n+j,numR-numL), tmp[i]-=numL, tmp[n+j]+=numL;
    for(int i=1;i<=n;i++){
        int fL=max(sum1[i]-mid,0), fR=sum1[i]+mid;
        add(S,i,fR-fL), tmp[S]-=fL, tmp[i]+=fL;
    }
    for(int i=1;i<=m;i++){
        int fL=max(sum2[i]-mid,0), fR=sum2[i]+mid;
        add(n+i,T,fR-fL), tmp[n+i]-=fL, tmp[T]+=fL;
    }
    add(T,S,1e+9);
    int Blnc=0;
    for(int i=1;i<=n+m+2;i++){
        if(tmp[i]>0) add(SS,i,tmp[i]), Blnc+=tmp[i];
                else add(i,TT,-tmp[i]);
    } 
    return Dinic(SS,TT)==Blnc;
}
int main(){
    freopen("bzoj2406.in","r",stdin);
    freopen("bzoj2406.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++){
        int x; scanf("%d",&x);
        sum1[i]+=x, sum2[j]+=x;
     }
    scanf("%d%d",&numL,&numR);
    ans=-1;
    int L=0,R=10000000;
    while(L<=R){
        int mid=(L+R)>>1;
        if(check(mid)) R=mid-1, ans=mid;
                  else L=mid+1; 
    }
    printf("%d\n",ans);
    return 0;
}