Description
Data Constraint
Solution
我們可以現二分答案。
對于一個二分的答案mid。我們對行和列分别進行讨論。
對于B矩陣的一行，滿足
|A−B|<=mid
A−mid<=B<=A+mid
，同時L*m<=B<=R *m。是以我們就可以找到B這一行的範圍[mi,mx]。當然要mi<=mx。把所有mi累加，把mx累加，我們就得到了隻滿足行情況的B矩陣的範圍。
列的情況同理。若最後行與列的範圍有交集，那麼久邵明一定有一種取值使B同時滿足行與列的要求，是以繼續二分。
現在我們得到了第一問的答案。怎麼求解。打個上下界網絡流！！我們源點往每一行連一條上界為A+mid下界為A-mid的邊，每一列往彙點連一條上界為A+mid下界為A-mid的邊，中間每一行向每一列連一條上界為R下界為L的邊。按正常的有源彙建個超級源超級彙，一個[l,r]的邊u->v變成超級源向v連l的邊，u往超級彙連l的邊，u->v連r-l的邊。彙點往源點連+∞的邊。跑一下最大流即可。
Code
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=e2+,maxn1=e5;
int a[maxn][maxn],b[maxn][maxn],s[maxn],s1[maxn],c[maxn],d[maxn*maxn];
int first[maxn1],last[maxn1],next[maxn1],value[maxn1],dui[maxn1],v[maxn1];
int n,m,i,t,j,k,l,x,y,z,r,mid,ll,rr,mi,mx,bz,mi1,mx1,ans,num,s2,ss,tt;
void lian(int x,int y,int z){
last[++num]=y;next[num]=first[x];first[x]=num;value[num]=z;
}
int dg(int x,int sum){
int t,p=sum,k;
if (x==tt) return sum;
for (t=first[x];t;t=next[t]){
if (d[last[t]]!=d[x]+ || !value[t]) continue;
k=dg(last[t],min(p,value[t]));
if (k){
value[t]-=k;value[dui[t]]+=k;p-=k;
if (!p) break;
}
}
if (p==sum) d[x]=-;
return sum-p;
}
int bfs(){
int i=,j=;v[]=ss;memset(d,,sizeof(d));d[ss]=;
while (i<j){
x=v[++i];
for (t=first[x];t;t=next[t])
if (d[last[t]]< && value[t]) v[++j]=last[t],d[v[j]]=d[x]+;
}
if (d[tt]>) return ;return ;
}
int main(){
//freopen("data.in","r",stdin);freopen("data.out","w",stdout);
scanf("%d%d",&n,&m);
for (i=;i<=n;i++)
for (j=;j<=m;j++)
scanf("%d",&a[i][j]),s[i]+=a[i][j],s1[j]+=a[i][j];
scanf("%d%d",&ll,&rr);
l=;
r=e7;
while (l<r){
mid=(l+r)/;mi1=mx1=mi=mx=;bz=;
for (i=;i<=n;i++){
t=max(s[i]-mid,ll*m),k=min(s[i]+mid,rr*m);
if (t>k){
bz=;break;
}
mi+=t;mx+=k;
}
for (i=;i<=m;i++){
t=max(s1[i]-mid,ll*n),k=min(s1[i]+mid,rr*n);
if (t>k){
bz=;break;
}
mi1+=t;mx1+=k;
}
if (mx1<mi || mi1>mx) bz=;
if (!bz) r=mid;
else l=mid+;
}
printf("%d\n",l);ans=l;bz=;t=n*m+;ss=t+;tt=ss+;
for (i=;i<=n;i++){
x=max(s[i]-l,ll*m),y=min(s[i]+l,rr*m);
lian(,i,y-x);lian(i,,);lian(ss,i,x);lian(i,ss,);lian(,tt,x);lian(tt,,);
}
for (i=;i<=m;i++){
x=max(s1[i]-l,ll*n),y=min(s1[i]+l,rr*n);
lian(i+n,t,y-x);lian(t,i+n,);lian(ss,t,x);lian(t,ss,);lian(i+n,tt,x);lian(tt,i+n,);
}
for (i=;i<=n;i++)
for (j=n+;j<=n+m;j++){
lian(i,j,rr-ll);lian(j,i,);lian(ss,j,ll);lian(j,ss,);lian(i,tt,ll);lian(tt,i,);
}
lian(ss,,e9+);lian(,ss,);lian(t,tt,e9+);lian(tt,t,);
for (i=;i<=num;i++)
if (i%2)dui[i]=i+,dui[i+]=i;
while (bfs()) dg(ss,e9+);
for (i=;i<=n;i++){
x=i;
for (t=first[x];t;t=next[t])
if (last[t]>n && last[t]<=n+m) b[i][last[t]-n]=ll+value[dui[t]];
}
for (i=;i<=n;i++){
for (j=;j<=m;j++)
printf("%d ",b[i][j]);
printf("\n");
}
}