BZOJ 2406 矩阵

发布于 2017-08-30  167 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2406

题意:给一个矩阵 A,构造另一个元素都在 [l,r] 的矩阵 B,矩阵 C=A-B。记 t1=C 每一列的元素和的绝对值的最大值,t2=C 每一行的元素和的绝对值的最大值。记 T=max(t1,t2),试构造矩阵 B 使得 T 最小。


我这题意简述的真是好啊...

最大值最小显然就是二分答案了,考虑 t2 的情况,合法的 mid 是这样的:

$$\left | \sum a_i-\sum b_i \right |\leq mid$$

即:

$$\sum a_i-mid\leq \sum b_i\leq \sum a_i+mid$$

这显然是上下界网络流的形式了,行列建边,判断可行流即可。

 


一个非常弱的准退役OIER