[BZOJ2127/Luogu1646]happiness(网络流)

发布于 2018-02-03  8 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2127/Luogu1646]happiness(网络流)

Description

高一一班的座位表是个n*m的矩阵,经过一个学期的相处,每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了,每个同学对于选择文科与理科有着自己的喜悦值,而一对好朋友如果能同时选文科或者理科,那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板,想知道如何分配可以使得全班的喜悦值总和最大。

Http

BZOJ
Luogu

Tag

网络流

解决思路

这一题类似的,先把求最大收益转化为求最小损失,即先把所有的收益都加起来,然后求一个最小的损失即最小割。
一个人选文还是选理分别与源汇点连边,假设源点\(S\)表示选文,汇点\(T\)表示选理,这个比较好处理,但是,与旁边的人的选择就不好处理了,因为这里两人同时选文和同时选理的收益是不一样的。
怎么办呢?总共只有\(4\)种可能,所以我们把这四种情况列出来。
设\(x->y\)表示\(x\)到\(y\)这条边上的容量,设\(u\)表示两人同时选文的收益,\(v\)为两人同时选理的收益,则有:
若两人同时选文,则割掉的边是\(x->T,y->T\),损失是\(v\)。
若两人同时选理,则割掉的边是\(S->x,S->y\),损失是\(u\)
若\(x\)文\(y\)理,则割掉的边是\(x->T,S->y,x->y\),损失是\(u+v\)
若\(x\)理\(y\)文,则割掉的边是\(S->x,y->T,y->x\)
综上,四个方程就是
\((x->T)+(y->T)=v \\ (S->x)+(S->y)=u \\ (x->T)+(S->y)+(x->y)=u+v \\ (S->x)+(y->T)+(y->x)=u+v\)
但是这个方程是无法直接解的。考虑到实际上不管是哪一组解都是可以的,不妨设\((x->T)==(y->T)==\frac{v}{2}\),同理有\((S->x)==(S->y)==\frac{u}{2}\),那么就有\((x->y)==(y->x)==\frac{u+v}{2}\)
由于除以二会导致可能出现小数,所以考虑把所有的容量先乘以二变成整数,最后求出最小割再除以二即可。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2127/Luogu1646]happiness(网络流)


HNCJ OIer 一枚