【LG3973】[TJOI2015]线性代数

题面

洛谷

题解

正常解法

一大堆矩阵乘在一起很丑对吧
化一下柿子：
\[ D=(A*B-C)*A^T\\Leftrightarrow D=\sum_{i=1}^n(\sum_{j=1}^na_j*b_{j,i}-c_i)*a_i\\Leftrightarrow D=\sum_{i=1}^n\sum_{j=1}^na_i*a_j*b_{i,j}-\sum_{i=1}^na_i*c_i \]
分析一下我们选或不选某个数的贡献：
因为\(\forall a_i\in{0,1}\)，所以我们可以将贡献算出
如果同时选\(i,j\)，则获得\(b_{i,j}+b_{j,i}\)的贡献
如果不选\(i\)，则减去\(c_i\)的贡献
这就是一个最大权闭合子图：
连边时，\(S\)连代表\((i,j)\)的点,容量\(b_{i,j}+b_{j,i}\)，
代表\(i\)的点连\(T\),容量\(c_i\)
而如果选\((i,j)\)必选\(i\)、\(j\)再连
\[ (i,j)\rightarrow i(cap=\infty)\(i,j)\rightarrow j(cap=\infty) \]
然后总和-最小割即可
然而因为下面的方法，我没有用最大流

奇怪的\(AC\)

\(\sum_{i=1}^n\sum_{j=1}^nb_{i,j}-\sum_{i=1}^n c_i\)
八行主程序：

int main () {
    N = gi(); int ans = 0;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++) ans += gi(); 
    for (int i = 1; i <= N; i++) ans -= gi();
    printf("%d\n", ans); 
    return 0; 
} 

【LG3973】[TJOI2015]线性代数

原文：https://www.cnblogs.com/heyujun/p/10281212.html