矩阵
给定一个 (n imes m) 的整数矩阵 (A) ，你需要构造一个 (n imes m) 的整数矩阵 (B) ，满足 (B) 中的每个元素 (B_{i,j}in [L, R]) 。
定义 (r(i) = |sum_{j=1}^{m}A_{i,j} - sum_{j=1}^m B_{i,j}|) ，即两个矩阵第 (i) 行元素和之差。
定义 (c(j)= |sum_{i=1}^n A_{i,j} - sum_{j=1}^m B_{i,j}|) ，即两个矩阵第 (j) 列元素和之差。
请求出 (max lbrace max_{i=1}^n r(i), max_{j=1}^m c(j) brace) 的最小值，并输出一组构造矩阵 (B) 的方案,使得这个最小值被取到。
若有多种合法的构造方案，你只需输出其中任意一组。
(n,mle 200, 0le Lle Rle 1000, 0le A_{i,j}le 1000)。
题解
把两个矩阵叠加到一起，每个格子((i,j))里的元素可以看成(A_{i,j}-R+x~(xin [0,R-L]))。
可以认为(r(i),c(j))有初始值，把(x)看成调整(r(i))和(c(j))的变量。
二分答案，因为(R-L)非负，并且(r(i),c(j))的需要的调整量一定属于某个非负区间，所以行列连边后就转化成了有上下界可行流。
CO int N=410,inf=1e9;
namespace flow{
int S,T;
struct edge {int y,c,a;};
vector<edge> to[N];
int dis[N];
IN void init(int n){
S=n-1,T=n;
for(int i=1;i<=T;++i) to[i].clear();
}
IN void link(int x,int y,int c){
to[x].push_back((edge){y,c}),to[y].push_back((edge){x,0});
to[x].back().a=to[y].size()-1,to[y].back().a=to[x].size()-1;
}
bool bfs(){
fill(dis+1,dis+T+1,inf),dis[T]=0;
deque<int> Q(1,T);
while(Q.size()){
int x=Q.front();Q.pop_front();
for(int i=0;i<(int)to[x].size();++i){
CO edge&e=to[x][i];
if(to[e.y][e.a].c and dis[e.y]>dis[x]+1)
dis[e.y]=dis[x]+1,Q.push_back(e.y);
}
}
return dis[S]<inf;
}
int dfs(int x,int lim){
if(x==T) return lim;
int rest=lim;
for(int i=0;i<(int)to[x].size();++i){
edge&e=to[x][i];
if(e.c and dis[e.y]==dis[x]-1){
int delta=dfs(e.y,min(e.c,rest));
if(!delta) {dis[e.y]=inf; continue;}
rest-=delta,e.c-=delta,to[e.y][e.a].c+=delta;
if(!rest) break;
}
}
return lim-rest;
}
int main(){
int ans=0;
while(bfs()) ans+=dfs(S,inf);
return ans;
}
}
int n,m,A[N][N],B[N][N];
int L,R,row[N],col[N];
int in[N],out[N];
bool solve(int lim){
flow::init(n+m+4);
int s=n+m+1,t=n+m+2;
flow::link(t,s,inf);
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j) flow::link(i,n+j,R-L);
fill(in+1,in+t+1,0),fill(out+1,out+t+1,0);
for(int i=1;i<=n;++i){
if(row[i]>=-lim) {flow::link(s,i,lim-row[i]); continue;}
out[s]+=-lim-row[i],in[i]+=-lim-row[i];
flow::link(s,i,2*lim);
}
for(int j=1;j<=m;++j){
if(col[j]>=-lim) {flow::link(n+j,t,lim-col[j]); continue;}
out[n+j]+=-lim-col[j],in[t]+=-lim-col[j];
flow::link(n+j,t,2*lim);
}
for(int i=1;i<=t;++i){
if(in[i]>out[i]) flow::link(flow::S,i,in[i]-out[i]);
else if(in[i]<out[i]) flow::link(i,flow::T,out[i]-in[i]);
}
flow::main();
for(int i=0;i<(int)flow::to[flow::S].size();++i){
CO flow::edge&e=flow::to[flow::S][i];
if(e.c>0) return 0;
}
for(int i=0;i<(int)flow::to[flow::T].size();++i){
CO flow::edge&e=flow::to[flow::T][i];
if(flow::to[e.y][e.a].c>0) return 0;
}
return 1;
}
int main(){
// freopen("mat.in","r",stdin),freopen("mat.out","w",stdout);
read(n),read(m);
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j) read(A[i][j]);
read(L),read(R);
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j) A[i][j]-=R;
int l=0,r=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j) row[i]+=A[i][j];
if(row[i]>0) l=max(l,row[i]);
r=max(r,abs(row[i]));
}
for(int j=1;j<=m;++j){
for(int i=1;i<=n;++i) col[j]+=A[i][j];
if(col[j]>0) l=max(l,col[j]);
r=max(r,abs(col[j]));
}
while(l<r){
int mid=(l+r)>>1;
if(solve(mid)) r=mid;
else l=mid+1;
}
printf("%d
",l);
solve(l);
for(int i=1;i<=n;++i){
for(int j=0;j<(int)flow::to[i].size();++j){
CO flow::edge&e=flow::to[i][j];
if(n+1<=e.y and e.y<=n+m) B[i][e.y-n]=R-(R-L-e.c);
}
}
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j) printf("%d%c",B[i][j],"
"[j==m]);
return 0;
}