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

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

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

这题,首先把题目那个式子的绝对值拆成两个限制,就成了网络流的上下界;

有上下界可行流原来只需要先流出下界,然后用超级源汇补足即可,原来的汇点向源点连一条下界0上界 inf 的边,就也流量守恒了;

竟然是枚举出错了囧,因为平时写的 S=0,所以枚举就是 S~T,但这回写的 S=n+1,枚举应该变成 1~T 啊!

代码如下:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int const xn=,xm=1e5+,inf=1e9;
int n,m,si[xn],sj[xn],hd[xn],ct=,to[xm],nxt[xm],c[xm],dis[xn];
int tmp[xn],a[xn][xn],cur[xn],L,R,S,T,SS,TT;
queue<int>q;
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return f?ret:-ret;
}
void ade(int x,int y,int z){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct; c[ct]=z;}
void add(int x,int y,int z){ade(x,y,z); ade(y,x,);}
bool bfs(int s,int t)
{
memset(dis,,sizeof dis);
dis[s]=; q.push(s);
while(q.size())
{
int x=q.front(); q.pop();
for(int i=hd[x],u;i;i=nxt[i])
if(!dis[u=to[i]]&&c[i])dis[u]=dis[x]+,q.push(u);
}
return dis[t];
}
int dfs(int x,int fl,int t)
{
if(x==t)return fl;
int ret=;
for(int &i=cur[x],u;i;i=nxt[i])
{
if(dis[u=to[i]]!=dis[x]+||!c[i])continue;
int tmp=dfs(u,min(fl-ret,c[i]),t);
if(!tmp)dis[u]=;
c[i]-=tmp; c[i^]+=tmp;
ret+=tmp; if(ret==fl)break;
}
return ret;
}
int dinic(int s,int t)
{
int ret=;
while(bfs(s,t))
{
memcpy(cur,hd,sizeof hd);
ret+=dfs(s,inf,t);
}
return ret;
}
bool ck(int mid)
{
ct=; memset(hd,,sizeof hd);
memset(tmp,,sizeof tmp);
for(int i=;i<=n;i++)
{
int l=max(,si[i]-mid),r=si[i]+mid;
add(S,i,r-l); tmp[S]-=l; tmp[i]+=l;
}
for(int j=;j<=m;j++)
{
int x=n+j,l=max(,sj[j]-mid),r=sj[j]+mid;
add(x,T,r-l); tmp[x]-=l; tmp[T]+=l;
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
add(i,n+j,R-L); tmp[i]-=L; tmp[n+j]+=L;
}
add(T,S,inf); int goal=;
for(int i=;i<=T;i++)//!S
if(tmp[i]>)add(SS,i,tmp[i]),goal+=tmp[i];
else if(tmp[i]<)add(i,TT,-tmp[i]);
return goal==dinic(SS,TT);
}
int main()
{
n=rd(); m=rd(); int l=,r=;
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],r+=a[i][j];
L=rd(); R=rd();
int ans; S=n+m+; T=n+m+; SS=n+m+; TT=n+m+;
while(l<=r)
{
int mid=((l+r)>>);
if(ck(mid))ans=mid,r=mid-;
else l=mid+;
}
printf("%d\n",ans);
return ;
}