题目大意
班级可视为 (n times m) 的矩阵,现进行文理分科。
- 位置 ([i, ; j]) 的人选文科会获得满意值 (art[i, ; j]),选理科会获得 (science[i, ; j])。
- 位置 ([i, ; j]) 的人及其下面的人均选择文科会额外获得满意值 (artColumn[i, ; j]),均选择理科会额外获得 (scienceColumn[i, ; j])。
- 位置 ([i, ; j])的人及其右面的人均选择文科会额外获得满意值 (artRow[i, ; j]),均选择理科会额外获得 (scienceRow[i, ; j])。
求最大满意值。
(1 leqslant n, ; m leqslant 100)
(其他数据 leqslant 5,000)
(直接从文理分科复制过来改了改。。。)
题目链接
题解
最大权闭合图。
先让所有人选择文科。
每个人拆为 (5) 个节点,分别表示改选理科满意值的变化量、改选后文科列额外满意值的损失量、改选后理科列额外满意值的增加量、改选后文科行额外满意值的损失量、改选后理科行额外满意值的增加量,分别记为节点种类 (1 sim 5)。对于每一个节点 (1),向其自己与下面的人的节点 (2) 连边,向其自己与右面的人的节点 (4);从其自己与下面的人的节点 (3)、其自己与右面的人的节点 (5) 向该节点的节点 (1) 连边。
(继续复制。。。)
文理分科的姊妹篇吗(说来这个的题号在文理分科前啊。。。)。。。
代码
代码中的行 R(row) 和列 C(column) 写反了。。。写之前还专门查的。。。