首页 > 代码库 > BZOJ 2406 二分+有上下界的网络流判定

BZOJ 2406 二分+有上下界的网络流判定

思路:

求出每行的和  sum_row

每列的和   sum_line

二分最后的答案mid

S->i  流量[sum_row[i]-mid,sum_row[i]+mid]

i->n+j 流量[L,R]

n+j->T 流量 [sum_line[i]-mid,sum_line[i]+mid]

套用有上下界的网络流 判一下就好了..

这是道有上下界网络流的裸题

//By SiriusRen#include <queue>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=205,M=222222;int n,m,a[N][N],sum_row[N],sum_line[N],L,R;struct Dinic{    int first[N*2],next[M],v[M],w[M],vis[N*2],tot,T,SS,TT,jy,du[N*2],all;    void Add(int x,int y,int z){w[tot]=z,v[tot]=y,next[tot]=first[x],first[x]=tot++;}    void add(int x,int y,int z){Add(x,y,z),Add(y,x,0);}    bool tell(){        memset(vis,-1,sizeof(vis)),vis[SS]=0;        queue<int>q;q.push(SS);        while(!q.empty()){            int t=q.front();q.pop();            for(int i=first[t];~i;i=next[i])                if(vis[v[i]]==-1&&w[i])                    vis[v[i]]=vis[t]+1,q.push(v[i]);        }return vis[TT]!=-1;    }    int zeng(int x,int y){        if(x==TT)return y;        int r=0;        for(int i=first[x];~i&&y>r;i=next[i])            if(vis[v[i]]==vis[x]+1&&w[i]){                int t=zeng(v[i],min(y-r,w[i]));                w[i]-=t,w[i^1]+=t,r+=t;            }        if(!r)vis[x]=-1;        return r;    }    int flow(){        int ans=0;        while(tell())while(jy=zeng(SS,0x3f3f3f3f))ans+=jy;        return ans;    }    bool check(int x){        memset(first,-1,sizeof(first)),        all=tot=0,T=n+m+1,SS=n+m+2,TT=n+m+3,        memset(du,0,sizeof(du));        add(T,0,0x3f3f3f3f);        for(int i=1;i<=n;i++)add(0,i,2*x),du[i]+=sum_row[i]-x,du[0]-=sum_row[i]-x;        for(int i=1;i<=m;i++)add(i+n,T,2*x),du[T]+=sum_line[i]-x,du[i+n]-=sum_line[i]-x;        for(int i=1;i<=n;i++)            for(int j=1;j<=m;j++)                add(i,j+n,R-L),du[j+n]+=L,du[i]-=L;        for(int i=0;i<=T;i++){            if(du[i]>0)add(SS,i,du[i]),all+=du[i];            else add(i,TT,-du[i]);        }if(flow()>=all)return 1;        return 0;    }}d;int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++){            scanf("%d",&a[i][j]);            sum_row[i]+=a[i][j];            sum_line[j]+=a[i][j];        }    scanf("%d%d",&L,&R);    int l=0,r=200000,ans=0;    while(l<=r){        int mid=(l+r)>>1;        if(d.check(mid))r=mid-1,ans=mid;        else l=mid+1;    }printf("%d\n",ans);}

 

BZOJ 2406 二分+有上下界的网络流判定