首页 > 题解 > bzoj 2406 矩阵

bzoj 2406 矩阵

Description

Input

第一行两个数n、m,表示矩阵的大小。
接下来n行,每行m列,描述矩阵A。
最后一行两个数L,R。
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

题解

最大值最小,想到二分答案。

每次二分一个答案mid,相当于$|\sum a_i – \sum bi| \le mid$

拆开$\sum a_i-mid\le \sum b_i\le \sum a_i+mid$

这就可以用可行流check了

每一行和每一列建一个点xi,yi

s->xi,[ai-mid,ai+mid]
yj->t,[aj-mid,aj+mid]
xi->yj,[L,R]

只要判断是否有可行流就行了


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×