Contest Info

practice link

Solutions

B. Yu-Gi-Oh!

题目大意：场面上有 \(n \leq 300\) 只决斗怪兽，每只怪兽是调整或非调整怪兽。第 \(i\) 只决斗怪兽的星数为 \(level_i\)，攻击力为 \(ATK_i\)。额外卡组中有 \(m \leq 300\) 种，数量不限的同调怪兽（既不是调整也不是非调整怪兽）。第 \(j\) 只同调怪兽的星数为 \(level_j\)，攻击力为 \(ATK_j\)。

一般来说，如果调整怪兽 \(i\) 和 非调整怪兽 \(j\) 的星数之和等于同调怪兽 \(k\) 的星数，那么玩家可以消耗调整怪兽 \(i\) 和非调整怪兽 \(j\)，以它们作为同调素材来同调召唤一只同调怪兽 \(k\)。但是一些同调怪兽的召唤是有限制的，即它必须含有给出的一种或者两种同调素材，保证给出的限制仍然满足一般的同调召唤的条件。求经过若干次同调召唤后，场面上留下的怪兽的攻击力之和最大值。

题解：新建一个源点 \(s\) 和汇点 \(t\)，从 \(s\) 向调整怪兽连流量为 \(1\)，费用为 \(0\) 的边，从非调整怪兽向 \(t\) 连流量为 \(1\)，费用为 \(0\) 的边。再在调整怪兽和非调整怪兽之间连流量为 \(1\)，费用为用它们为同调素材能召唤出的攻击力最高的同调怪兽的攻击力减去它们的攻击之和的边（如果这个费用小于等于 \(0\) 就不连边）。然后跑最大费用可行流，答案就是最大费用加上初始局面的攻击力。

D. Asa’s Chess Problem

题目大意：有一个 \(n \times n\) （\(n\leq50\)，且 \(n\) 为偶数）的棋盘，每个位置非黑即白。棋盘中的格子被分成了 \(\frac{n\times n}{2}\) 个 pair，棋盘中每个位置属于且只属于一个 pair，每个 pair 中的两个位置一定在同一行或者同一列。要求进行若干次操作，每次操作交换属于同一个 pair 的两个位置。要使棋盘第 \(i\) 行的黑格子个数 \(R_i \in [Rl_i,Rh_i]\)，并且第 \(i\) 列的黑格子个数 \(C_i \in [Cl_i,Ch_i]\)。问是否有解，如果有解求最少的操作次数。

题解：转化为有下界的最小费用可行流问题。对棋盘每行每列都建一个点：

• 从源点 \(s\) 向行和列连费用为 \(0\) 的边，流量上下界都等于原来棋盘中对应的黑格子个数
• 从行和列向汇点 \(t\) 连费用为 \(0\) 的边，流量下界和上界为题目中的对应限制
• 考虑黑白颜色不同的 pair，从黑色的位置的行或列（取不同的那一维坐标）向白色的位置的行或列连费用为 \(1\)，下界为 \(0\)，上界为 \(1\) 的边。

然后从 \(s\) 到 \(t\) 的最小费用可行流就是答案（需要先判断下界是否都流满了）。