BZOJ 2406 矩阵

Description

Input

Output

Sample Input

Sample Output

HINT

Source

二分+网络流~

求的是最小的最大值，二分答案。

已知答案的话，abs(sum{a[i]}-sum{b[i]})<=mid，化简得sum{a[i]}-mid<=sum{b[i]}<=sum{a[i]}+mid，可以用有源汇有上下界的网络流来做。

建边：s到i，下界sum{a[i]}-mid，上界sum{a[i]}+mid；

i+n到t，下界sum{b[i]}-mid，上界sum{b[i]}+mid；

i到j+n，下界L，上界R。

然后就是正常的有源汇有上下界的网络流的套路了~

参考神犇Clove_unique的代码，优化了不少地方，比如用du[]代替in[]和out[]，以及不用记录mx和mn，直接记录在v[i]上。

数组要开大~

考试的时候居然看错了题……直接写了个贪心不知道WA成什么样了……所以说读题很重要啊！

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define inf 999999999int n,m,x,L,R,fi[410],w[100100],ne[100100],v[100100],cnt;
int xx[201],yy[201],dis[410],s,t,S,T,lascnt,du[410],l,r,ans;
bool b[410];queue<int> q;int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}void add(int u,int vv,int val)
{w[++cnt]=vv;ne[cnt]=fi[u];fi[u]=cnt;v[cnt]=val;w[++cnt]=u;ne[cnt]=fi[vv];fi[vv]=cnt;v[cnt]=0;
}bool bfs()
{memset(dis,-1,sizeof(dis));dis[S]=0;q.push(S);while(!q.empty()){int k=q.front();q.pop();for(int i=fi[k];i;i=ne[i])if(dis[w[i]]==-1 && v[i]>0){dis[w[i]]=dis[k]+1;q.push(w[i]); }}return dis[T]==-1 ? 0:1;
}int findd(int u,int vv)
{if(u==T) return vv;int now=0,kkz;for(int i=fi[u];i;i=ne[i])if(dis[w[i]]==dis[u]+1 && v[i]>0 && (kkz=findd(w[i],min(vv-now,v[i])))){v[i]-=kkz;v[i^1]+=kkz;now+=kkz;if(now==vv) return now;}if(!now) dis[u]=-1;return now;
}bool jud(int u)
{int now=0,totnum=0,kkkkk=0;cnt=1;memset(fi,0,sizeof(fi));memset(du,0,sizeof(du));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=1;i<=n;i++) add(s,i,2*u),du[i]-=xx[i]-u,du[s]+=xx[i]-u;for(int i=1;i<=m;i++) add(i+n,t,2*u),du[t]-=yy[i]-u,du[i+n]+=yy[i]-u;add(t,s,inf);lascnt=cnt;for(int i=s;i<=t;i++)if(du[i]<0) add(S,i,-du[i]),totnum-=du[i];else if(du[i]>0) add(i,T,du[i]),kkkkk+=du[i];if(kkkkk!=totnum) return 0;while(bfs()) now+=findd(S,inf);return now==totnum;
}int main()
{n=read();m=read();t=n+m+1;S=n+m+2;T=n+m+3;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) x=read(),xx[i]+=x,yy[j]+=x;L=read();R=read();r=2000000;while(l<=r){int mid=l+r>>1;if(jud(mid)) ans=mid,r=mid-1;else l=mid+1;}printf("%d\n",ans);return 0;
}