bzoj 2406 矩阵——有源汇上下界可行流

时间：2023-03-09 19:32:53
bzoj 2406 矩阵——有源汇上下界可行流

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2406

二分答案。把 b 的 n 个行作为一排， m 个列作为一排，每行和每列之间连上下界为 L , R 的边，源点向每行连以 “ a 的该行的值的和” 加/减 mid 为上下界的边，每列向汇点连以 “ a 的该列的值的和” 加/减 mid 为上下界的边；然后跑可行流就行了。

自己把和超级源点及超级汇点的无关的边先连好了，到时候改一改容量就行了。但别忘了把 hd[ ] , cap[ ] , xnt , tp[ ] 都赋回原来的值。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=,M=N*N<<,INF=4e7+;

int n,m,yhd[N<<],hd[N<<],xnt=,cur[N<<],bj,to[M],nxt[M],ycap[M],cap[M],dy[N<<];

int sh[N],sl[N],s,t,ss,tt,tp[N<<],ttp[N<<];

int dfn[N<<],q[N<<],he,tl;

int Mn(int a,int b){return a<b?a:b;}

int Mx(int a,int b){return a>b?a:b;}

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

void add(int x,int y,int z)

{

  to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;cap[xnt]=z;

  to[++xnt]=x;nxt[xnt]=hd[y];hd[y]=xnt;cap[xnt]=;

}

bool bfs(int mid)

{

  memset(dfn,,sizeof dfn);dfn[ss]=;

  q[he=tl=]=ss;

  while(he<=tl)

    {

      int k=q[he++];

      for(int i=hd[k],v;i;i=nxt[i])

    if(!dfn[v=to[i]]&&cap[i])

      dfn[v]=dfn[k]+,q[++tl]=v;

    }

  return dfn[tt];

}

int dinic(int cr,int flow)

{

  if(cr==tt)return flow;

  int use=;

  for(int& i=cur[cr],v;i;i=nxt[i])

    if(dfn[v=to[i]]==dfn[cr]+&&cap[i])

      {

    int tmp=dinic(v,Mn(flow-use,cap[i]));

    if(!tmp)dfn[v]=;

    use+=tmp;cap[i]-=tmp;cap[i^]+=tmp;

    if(use==flow)return use;

      }

  return use;

}

bool chk(int mid)

{

  xnt=bj;memcpy(ttp,tp,sizeof tp);

  memcpy(hd,yhd,sizeof yhd);//

  for(int i=;i<=bj;i++)cap[i]=ycap[i];///

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

    {

      int l=Mx(sh[i]-mid,),r=sh[i]+mid;

      cap[dy[i]]=r-l;cap[dy[i]^]=;

      ttp[i]+=l;ttp[s]-=l;

    }

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

    {

      int l=Mx(sl[i]-mid,),r=sl[i]+mid;

      cap[dy[i+n]]=r-l;cap[dy[i+n]^]=;

      ttp[i+n]-=l;ttp[t]+=l;

    }

  int val=;

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

    if(ttp[i]>)add(ss,i,ttp[i]),val+=ttp[i];

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

  while(bfs(mid))

    memcpy(cur,hd,sizeof hd),val-=dinic(ss,INF);

  return !val;

}

int main()

{

  n=rdn();m=rdn();

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

    for(int j=;j<=m;j++)

      d=rdn(),sh[i]+=d,sl[j]+=d;

  int L=rdn(),R=rdn();

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

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

    for(int j=;j<=m;j++)

      add(i,j+n,R-L),tp[i]-=L,tp[j+n]+=L;

  add(t,s,INF);

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

    add(s,i,),dy[i]=xnt-;

  for(int i=n+,j=n+m;i<=j;i++)

    add(i,t,),dy[i]=xnt-;

  bj=xnt;

  memcpy(yhd,hd,sizeof hd);

  for(int i=;i<=bj;i++)ycap[i]=cap[i];

  int l=,r=2e5+,ans;

  while(l<=r)

    {

      int mid=l+r>>;

      if(chk(mid))ans=mid,r=mid-;

      else l=mid+;

    }

  printf("%d\n",ans);

  return ;

}

相关文章