Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom3月前

05/20
15:12
上下界网络流 二分法

[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

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

二分答案,用上下界网络流来验证

s->xi (ai - mid, ai + mid)  yj->t (aj - mid, aj + mid)  xi -> yj (L, R)

判断是否有可行流量

 

[bzoj 2406] 矩阵