题解 P3973 【[TJOI2015]线性代数】

· · 题解

看到这道题，我们先来画一下柿子。

D=(A*B-C)*A^T D=\sum_{i=1}^n(\sum_{j=1}^na_j*b_{j,i}-c_i)*a_i D=\sum_{i=1}^n\sum_{j=1}^na_i*a_j*b_{i,j}-\sum_{i=1}^na_i*c_i

柿子画到这里，我们可以看出，对于每个a_i，选0的时候没有贡献，选1的时候会带来c_i的损失，但是对于每一个同样选1的a_j,会带来b_{j,i}+b_{i,j}的贡献。

结合数据范围n\leq500,可以联想到最小割。

这里我们假设S集是a_i选0，T集是a_i选1。一开始我们获得了所有b的收益，我们要让损失最小化。

列式子

$(2)ax+ay=b_{x,x}+b_{x,y}+b_{y,x}+b_{y,y}$ (都选0的时候损失为$b$数组) $(3)ax+by+v=b_{x,x}+b_{x,y}+b_{y,x}+c_y 可以解出对于每一组$(x,y) ax=b_{x,x}+\frac{b_{x,y}+b_{y,x}}{2} ay=b_{y,y}+\frac{b_{x,y}+b_{y,x}}{2} bx=c_x by=c_y v=\frac{b_{x,y}+b_{y,x}}{2}

对于每一组(x,y),我们需要把割ax和ay的损失累加起来。

ax=b_{x,x}+\frac{\sum_{i=1}^n(i!=x)b_{x,i}+b_{i,x}}{2}=\frac{\sum_{i=1}^nb_{x,i}+b_{i,x}}{2}

这样建图就非常明显了，为了避免有小数的出现，我们将流量翻倍。

从源点S往每个点i连接流量为b数组第i行和第i列的权值总和的边。

每个点i往汇点T连接流量为c_i*2的边。

每一对点(i,j)之间连流量为b_{i,j}+b_{j,i}的双向边。

最后答案为\sum_{i=1}^n\sum_{j=1}^nb_{i,j}-\frac{Maxflow(S,T)}{2}

时间复杂度O(Maxflow(n,n^2))