BZOJ 3996 [TJOI2015] 线性代数

发布于 2017-05-16  139 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3996

题意:给出一个 n*n 的矩阵 A,1*n 的矩阵 C,求出一个 1*n 的 01 矩阵 A,使得\(D=(A*B-C)*A^T\) 最大,输出 D...


稍微化简一下\(D=A*B*A^T-C*A^T\),发现 A 是一个 01 矩阵,所以这个问题可以这么表达:

对于 n 个物品,选择 i 物品的代价是\(c_i\),同时选择 i,j 的收益是\(b_{ij}\) 那么这是一个经典的 最大权闭合图 模型了,今天算是学习了一个...

建图方式是这样的:对于每个\(b_{ij}\),在源点与点 ij 间连一条权值为\(b_{ij}\) 的边... 在点 ij 与点 i,j 间分别连一条权值为 inf 的边

对于每个\(c_i\),在汇点和 i 点间连一条权值为\(c_i\) 的边,最小割即可,代码如下

 


一个非常弱的准退役OIER