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

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

@krydom10月前

09/11
13:26
二分法 最大流

[bzoj 4443] [Scoi2015]小凸玩矩阵

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 小凸和小方是好朋友,小方给小凸一个N*M(N<=M)的矩阵A,要求小秃从其中选出N个数,其中任意两个数字不能在同一行或同一列,现小凸想知道选出来的N个数中第K大的数字的最小值是多少。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行给出三个整数N,M,K
接下来N行,每行M个数字,用来描述这个矩阵

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

如题

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

3 4 2
1 5 6 6
8 3 4 3
6 8 6 3

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

3

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

1<=K<=N<=M<=250,1<=矩阵元素<=10^9

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

二分答案,每次判定用网络流

设<=mid的数是可以取的,只要能取的数大于要求就是可行的

c++:

pascal:

 

[bzoj 4443] [Scoi2015]小凸玩矩阵