TJOI2015

只想看代码的直接翻到最下面


BZOJ3996: [TJOI2015]线性代数

一眼最小割,首先计算出答案 [tex]ans=\left ( \sum_{i=1}^{n}\sum_{i=1}^{n}A_iA_jB_{j,i}\right )-\sum_{i=1}^{n}A_iC_i [/tex] 然后对于所有[tex]i<j[/tex],连边[tex]<S,i,B{i,j}+B{j,i}>[/tex],[tex]<S,j,B{i,j}+B{j,i}>[/tex],[tex]<i,j,B{i,j}+B{j,i}>[/tex],[tex]<j,i,B{i,j}+B{j,i}>[/tex]

对于所有[tex]i[/tex],连边:[tex]<i,T,C_i*2>[/tex]

做最小割得到[tex]c[/tex],则[tex]ans=\left ( \sum B_{i,j} \right )-\frac{c}{2}[/tex]

继续阅读