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]

继续阅读

省选题解 bzoj 省选 TJOI Comments(2) 2016年2月03日 23:29