当前位置: 代码迷 >> 综合 >> BZOJ 2406 矩阵
  详细解决方案

BZOJ 2406 矩阵

热度:76   发布时间:2024-01-19 01:57:56.0

Description

Input

第一行两个数nm,表示矩阵的大小。

接下来n行,每行m列,描述矩阵A

最后一行两个数LR

Output

第一行,输出最小的答案;

Sample Input

2 2

0 1

2 1

0 1

Sample Output

1

HINT

对于100%的数据满足N,M<=200,0<=L<=R<=1000,0<=Aij<=1000


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;
}