版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

title: "题解 - [Luogu P3973] [TJOI2015] 线性代数" categories:

• 算法竞赛
• 题解 tags:
• 算法竞赛
• 题解
• 洛谷
• 省选
• TJOI
• 数学
• 代数
• 矩阵
• 构造
• 图论
• 网络流
• 最小割
• 二分图 date: 2022-10-31 21:38:14

题目链接

原始题面

题目描述

为了提高智商, ZJY 开始学习线性代数

她的小伙伴菠萝给她出了这样一个问题: 给定一个 $n \times n$ 的矩阵 $B$ 和一个 $1 \times n$ 的矩阵 $C$. 求出一个 $1×n$ 的 01 矩阵 $A$, 使得 $D=(A×B-C)×A^{\sf T}$ 最大, 其中 $A^{\sf T}$ 为 $A$ 的转置, 输出 $D$

输入格式

第一行输入一个整数 $n$. 接下来 $n$ 行输入 $B$ 矩阵, 第 $i$ 行第 $j$ 个数代表 $B$ 接下来一行输入 $n$ 个整数, 代表矩阵 $C$. 矩阵 $B$ 和矩阵 $C$ 中每个数字都是不过 $1000$ 的非负整数

输出格式

输出一个整数, 表示最大的 $D$

样例 #1

样例输入 #1

3
1 2 1
3 1 0
1 2 3
2 3 7

样例输出 #1

2

提示

• 对于 $30\%$ 的数据, $n \leq 15$;
• 对于 $100\%$ 的数据, $1 \leq n \leq 500$;
• 另外还有两组不计分的 hack 数据, 放在 subtask 2 中, 数据范围与上面一致

解题思路

式子不难写出来, 即求:

$$ \max_{a_i\in{0,1}}\left{\sum_i\sum_j a_iajb{ij}-\sum_i a_ic_i\right} $$

注意到如果 $a_i$ 为 $1$ 则答案会减 $ci$, 而如果答案包含 $b{ij}$ 的话则需选 $a_i$ 和 $a_j$

所以我们这样建一个二分图:

• 点集 $U$ 含 $n^2$ 个点, 内部元素记作 $u_{ij}$, $i,j\in 1..n$
• 点集 $V$ 含 $n$ 个点, 内部元素记作 $v_i$, $i\in 1..n$
• $u_{ij}$ 和 $v_i$, $v_j$ 连边, 边权设为 $\infty$

另外取源点 $s$ 和汇点 $t$, 将 $s$ 和点集 $U$ 中所有点连起来, $t$ 和点集 $V$ 所有点连起来, 边 $(s,u{ij})$ 的权为 $b{ij}$, 边 $(t,v_i)$ 的权为 $c_i$

接下来求这个图的最小割

• 显然 $(u_{ij},v_k)$ 不在最小割内
• 若 $(s,u{ij})$ 在最小割内, 则说明最终答案不包含 $b{ij}$
• 若 $(t,v_i)$ 在最小割内, 则说明最终答案要减去 $c_i$

最终答案即为 $\sum_i\sumj b{ij}$ 减去最小割的边权和

由于最终建的图是二分图, 所以 Dinic 复杂度是 $O(n^3)$ 的

代码参考