[POJ 3308]

Paratroopers

典型的最小割模型题目。做之前先读了国家集训队论文《最小割模型在信息学竞赛中的应用》。

题目大意是,有一个m*n的网格,m行和n列各对应一个权值。网格里面有l个点,如何在m行和n列中选择某些行列,使所有的点被覆盖,且使行列权值之积最小。

建图时S连所有行,E连所有列,行和列之间的边则对应原图的点且容量为无穷。这样便能应用最小割模型,得到的点集划分中割边必定为有穷边,且对应着原图中选中的行或列,使原图中每个点都能被覆盖(不能同时到S、E可达)。这里由于所求是作乘,将其取log,便转换成加法运算了。用EK求得最大流后,再从S点出发作DFS,就得到了实际的最小割方案,再依次检查遍历情况作乘即可。

不知为何c++竟然没有log2,CE了一次…T__T