感觉要做出来这个题,需要一定的线代芝士
首先,我们来观察这个柿子。
我们将\(B\)的权值看作是收益的话,\(C\)的权值就是花费。
根据矩阵乘法的原理,只有当\(a[i]和a[j]\)都为\(1\)的时候,才能够获取到\(a[i][j]\)代价,而把\(a[i]\)弄成1,又会付出\(c[i]\)的代价。
那这不就是一个经典的最大全闭合子图模型吗?
我们令\(S \rightarrow (i,j)\)这个坐标对应的点。流量是\(b[i][j]\),表示割去这个边,就舍弃了\(b[i][j]\)的收益
然后
\(i\rightarrow t\),流量是
\(c[i]\),表示如果这一位是1,要付出
\(c[i]\)的代价。
然后
\((i,j) \rightarrow i,(i,j)\rightarrow j\) 流量是
\(inf\) 因为依赖关系没法取消
// luogu-judger-enable-o2#include #include #include #include #include #include #include