题目:
高一一班的座位表是个n*m的矩阵,经过一个学期的相处,每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了,每个同学对于选择文科与理科有着自己的喜悦值,而一对好朋友如果能同时选文科或者理科,那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板,想知道如何分配可以使得全班的喜悦值总和最大。
分析:
首先不用想,这肯定是个最小割……不妨将其解题过程记录下来,以作为一个典型的最小割模型题。
“最小割”求的是一个“最小”的值,而本题需要最大化喜悦值之和,所以很显然,在最小割中被割掉的边应该意味着“放弃该喜悦值”。也就是说,最小割是放弃掉的所有喜悦值。
首先,为了简单起见,我们不妨选取一对相邻点进行研究。不妨设是这样的:
其中S是源点,x,y是我们研究的两个点(也就是原问题中的两个学生),T是汇点。为了方便起见,没有画出边。
文中可能会用到一些符号:w(a,b)表示边(a,b)的容量,x选文的喜悦值为W_x文,x,y都选文的额外喜悦值是W_同文,以此类推。
最小割模型常用的一个手段是:每个点都需要在“在S集”和“在T集”两个事件中选一个。我们规定,“在S集”代表学文,“在T集”代表学理。
那么总的快乐值是:W_x文 + W_x理 + W_y文 + W_y理 + W_同文 +W_同理,割值就是从其中扣掉的快乐值。
下面考虑四种情况:
①x在S,y在S:
割边容量之和:w(x,T) + w(y,T)
“放弃的快乐值”之和:W_x理 + W_y理 + W_同理 (两个人同时学文)
即:w(x,T) + w(y,T) = W_x理 + W_y理 + W_同理
②x在S,y在T:
w(x,T) + w(S,y) + w(x,y) = W_x理 + W_y文 + W_同文 + W_同理
类似可以推出后两种情况:
③x在T,y在S:w(S,x) + w(y,T) + w(y,x) = W_x文 + W_y理 + W_同文+ W_同理
④x在T,y在T:w(S,x) + w(S,y) = W_x文 + W_y文 + W_同文
把四种情况写在一起:
①SS:w(x,T) + w(y,T)= W_x理 + W_y理 + W_同理
②ST:w(x,T)+ w(S,y) + w(x,y) = W_x理 + W_y文 + W_同文 + W_同理
③TS:w(S,x)+ w(y,T) + w(y,x) = W_x文 + W_y理 + W_同文 + W_同理
④TT:w(S,x)+ w(S,y) = W_x文 + W_y文 + W_同文
然后,怎么设置这些边的容量呢?
我们看①,左边有两项,右边有三项。
秉承“对称”的思想,我们令:
w(x,T) = W_x理 + 0.5W_同理,
w(y,T) = W_y理+ 0.5W_同理。
类似地,
w(S,x) = W_x文 +0.5W_同文,
w(S,y) = W_y文 +0.5W_同文。
然后我们检查②和③。以②为例,将w(x,T)和w(S,y)代入并化简:
w(x,y) = 0.5 ( W_同文 + W_同理 )
看上去还不错!同样地由③得:
w(y,x) = 0.5 ( W_同文 + W_同理 )
把x,y扩展至整张棋盘:
对于某个人(i,j),设它对应的顶点是x。
连边(S,x),容量为:W_x理 + 0.5 ( x和所有邻居的W_同理之和)
连边(x,T),容量为:W_x文 + 0.5 ( x和所有邻居的W_同文之和 )
对于某两个相邻的人x和y(y可能在x的上下左右),
连边(x,y),容量为:0.5 ( W_同文 + W_同理 )
用所有的快乐值之和(其实就是输入的那六个矩阵的所有元素之和)减去最小割(即最大流)的值即为答案。这里有一点细节:实数容量的网络流不好求,可以把所有边的容量*2,最后输出答案时/2即可。
代码1:
其实还有另外一种方法。
回到①的那种情况。我们将整张棋盘黑白染色,那么x,y中有且仅有一个是黑的。
不妨设x黑,那么令:
w(x,T) = W_x理 + W_同理
w(y,T) = W_y理
类似地,y一定为白色,令:
w(S,x) = W_x文
w(S,y) = W_y文 + W_同文
(把W_同文加在w(S,x)上其实也行,但这并不重要)
将其代入②,③:
w(x,y) = 0
w(y,x) = W_同文 + W_同理
类似,对于一般的棋盘:
某黑格x:
w(x,T) = W_x理 + ( x和所有邻居的W_同理之和 )
w(S,x) =W_x文
某白格y:
w(y,T) = W_y理
w(S,y) = W_y文 + ( y和所有邻居的W_同文之和 )
对于相邻的两人x,y,其中x黑y白:
w(x,y) = 0
w(y,x) = W_同文 + W_同理
代码2:
还有一个代码,是上面所说把W_同文也加到w(S,x)上的。
代码3:
测试结果是:2跑得最快,3和1差不多,都比较慢。这是因为,2对于每对邻居只建了一条边,而1,3都是建了两条。