以下的描述中可能会把行和列弄反,请不要过于纠结.
[题目描述]
给你2个n*m的矩阵A和B,求一个矩阵C,满足:Ai,j<=Ci,j<=Bi,j,且C矩阵每行的和的绝对值的最大值与差的最大值最小.
[题解]
这道题还是很好想的,只要有一点线性规划的基础知识就行了.
没有的可以看一下我上一篇文章.
显然,我们先令Di,j=Ci,j+k,其中k是一个充分大的数使得Di,j的下界非负.
然后,我们二分这个ans,原问题变为:求一个矩阵D,满足:Li,j<=Di,j<=Ri,j,Li,j非负,且每行的和小于一个数,每列的和小于一个数.
先不考虑绝对值,写成线性规划是:
s.t. sigma(Di,j)<=F[i],1<=j<=n,对每个i (1)
sigma(Di,j)<=G[j],1<=i<=m,对每个j (2)
A[i,j]<=D[i,j]<=B[i,j] (3)
很明显,除了(3)以外,所有变量出现了2次,于是我们用之前用过的方法进行代数变换,约束变成这个样子:
s.t.sigma(Di,j)-xi=0,1<=j<=n,对每个i (1)
sigma(Di,j)-yi=0,1<=i<=m,对每个j (2)
A[i,j]<=D[i,j]<=B[i,j] (3)
0<=xi<=F[i],0<=yi<=G[i] (4)
然后,用类似的方法构图,对每行每列建立一个点,从原点向每行连一条流量为F[i]的边,从每列向汇点连流量为G[i]的边,从第i行向第j列连一条上界为Bi,j,下界为Ai,j的边,求一次可行流即可.不过,光用可行流判断似乎太浪费了,注意到对每个ans,行与列之间的边是不变的,而ans越优,对行列的限制就越紧,所以ms做一遍最小流就行了.不过还没有实现,不知道能不能做.
至于绝对值的问题,再加一个下界就行了.
//事实证明,只做一遍网络流是可行的,有人好像A掉了.出题需谨慎啊.