【算法】二分+有源汇上下界可行流

【题解】

 题解参考：

#include
      
       #include
       
        #include
        
         using namespace std;const int inf=0x3f3f3f3f,maxn=600;int n,first[maxn],q[1010],cur[maxn],in[maxn],S,T,s,t,tot=1,d[maxn],Aline[maxn],Alie[maxn],m,L,R;struct edge{
    int from,v,flow;}e[600010];void insert(int u,int v,int flow){tot++;e[tot].v=v;e[tot].flow=flow;e[tot].from=first[u];first[u]=tot; tot++;e[tot].v=u;e[tot].flow=0;e[tot].from=first[v];first[v]=tot;}bool bfs(){    memset(d,-1,sizeof(d));    int head=0,tail=1;q[0]=S,d[S]=0;    while(head
         
          1000)head=0;         for(int i=first[x];i;i=e[i].from)          if(e[i].flow&&d[e[i].v]==-1)           {               d[e[i].v]=d[x]+1;               q[tail++]=e[i].v;if(tail>1000)tail=0;           }     }    return d[T]!=-1;}int dinic(int x,int a){    if(x==T||a==0)return a;    int flow=0,f;    for(int& i=cur[x];i;i=e[i].from)     if(e[i].flow&&d[e[i].v]==d[x]+1&&(f=dinic(e[i].v,min(a,e[i].flow)))>0)      {          e[i].flow-=f;          e[i^1].flow+=f;//不要写反了           a-=f;          flow+=f;          if(a==0)break;      }    return flow;}bool work(int x){    tot=1;    memset(first,0,sizeof(first));    memset(in,0,sizeof(in));    S=501,T=502;    for(int i=1;i<=n;i++)     {         insert(s,i,2*x);         in[s]-=Aline[i]-x;         in[i]+=Aline[i]-x;     }    for(int i=1;i<=m;i++)     {         insert(i+200,t,2*x);         in[i+200]-=Alie[i]-x;         in[t]+=Alie[i]-x;     }    for(int i=1;i<=n;i++)     {         for(int j=1;j<=m;j++)          {              insert(i,j+200,R-L);              in[i]-=L;in[j+200]+=L;          }     }    insert(t,s,inf);    int Sout=0;    for(int i=s;i<=t;i++)     {         if(in[i]>0)insert(S,i,in[i]),Sout+=in[i];         if(in[i]<0)insert(i,T,-in[i]);     }    int ans=0;    while(bfs())     {         for(int i=s;i<=T;i++)cur[i]=first[i];         ans+=dinic(S,inf);     }    if(ans==Sout)return 1;    return 0;}int main(){    scanf("%d%d",&n,&m);    s=0,t=500;    for(int i=1;i<=n;i++)     {         int v=0;         for(int j=1;j<=m;j++)          {              int u;              scanf("%d",&u);              Alie[j]+=u;v+=u;          }         Aline[i]=v;     }    scanf("%d%d",&L,&R);    int l=0,r=200000;    while(l
          
           >1;         if(work(mid))r=mid;          else l=mid+1;     }    printf("%d",l);    return 0;}