【BZOJ3996】【TJOI2015】线性代数

又是一道不会做的网络流。。

怎么看都没看出是网络流啊。。= =

观察式子可以发现,结果是

$$\sum_{i=1}^{n}\sum_{j=1}^{n}A_iA_jB_{i,j}-\sum_{i=1}^{n}A_iC_i$$

听说这是经典最小割模型?

\(A_i\)表示是否选择第\(i\)个物品,那么上式就是说,选择\(i\)的代价是\(C_i\),同时选择\(i\)和\(j\)可以得到\(B_{i,j}\)的收益

那么建图。。对于这种二元逻辑关系可以用最小割

每对\((i,j)\)建点,从\(S\)向每个\(i\)连边,权值为\(c_i\);从每个\((i,j)\)向\(T\)连边,权值为\(B_{i,j}\);从\(i\)和\(j\)向\((i,j)\)连无穷边。

令\((i,j)\)被割掉表示没有得到这个收益,\(i\)被割掉表示选择了\(i\)。那么可以发现,如果\((i,j)\)要不被割掉,那么\(i\)和\(j\)都要被选择。

那么答案就是\(\sum_{i=1}^{n}\sum_{j=1}^{n}B_{i,j}-最小割\)。

说点什么

您将是第一位评论人!

提醒
wpDiscuz