zcmimi's blog

arrow_back最小割共2篇文章

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

总和减去最小割即为答案

最小割删掉的边就是要减去的值,这样就可以最小化要减去的值,即答案最大化

那我们如何构造这张图呢?

  1. ST \xrightarrow{\text{选文科的值}} (i,j) \xrightarrow{\text{选理科的值}}ED

  2. ST \xrightarrow{\text{同时选文科的额外快乐}}new,new\rightarrow(i,j),new\rightarrow(i+1,j)(其他同理)

  3. (i,j)\rightarrow new,(i+1,j)\rightarrow new,new \xrightarrow{\text{同时选理科的额外快乐}}ED(其他同理)

每个点只能选择文科或理科,当某个点选择了文科,那么它向理科(ED)的边都应该要被断开。

它直接连向ED的边、它和别的点组合连向ED的边都要切断

这些边的权值就会从最终答案中减去

infinf同时选文科选理科选文科同时选理科infinf选理科选文科ST(i,j)ED(i+1,j)newnew'
avatar
zc
2020-01-18 21:03:00
查看原题

点击跳转

[国家集训队]happiness有点像

而且建图更加简化了

答案为总和减去最小割

(i+j)\&1,(i',j')(i,j)相邻,黑白染色建图

st\xrightarrow{A} (i,j)\xrightarrow{B}ed

st\xrightarrow{B} (i',j')\xrightarrow{A}ed

(i,j) \xleftrightarrow{c_{i,j}+c_{i',j'}} (i',j')

ABBAc[i][j]+c[i'][j']c[i][j]+c[i'][j']sti,ji',j'ed

假设(i,j)选择A,那么要断开(i,j)\rightarrow t,(i,j)\rightarrow (i',j')

这些边上的权值会从答案中减去

最小割可以最小化要减去的权值,所以答案最大

1/1
Search
search