bzoj 4873: [Shoi2017]寿司餐厅 网络流 最大闭合子权图

这题考场上看出来是网络流了,也看出来是最大闭合子权图了,然后建图有一些差错,dinic 神TMD细节写错一直死循环……….然后GG。。

建图还是比较显然的。我们考虑对于每一个区间[i,j]连向[i+1,j] 和[i,j – 1]。如果i == j 就连向寿司i。然后每个寿司连向对应的代号。我们现在建出了图。我们考虑,对于最大闭合子权图问题,每个点考虑一个点权,寿司是负的对应代号,代号是负的对应mx^2。区间是其dij,然后对于点权是正的,从s连边到他,对于点权是负的,连边到T。流量为点权绝对值。然后把所有的dij正的求和,然后减去最小割即可。

“bzoj 4873: [Shoi2017]寿司餐厅 网络流 最大闭合子权图”的2个回复

发表评论