题解：P7056 [NWRRC 2015] Insider's Information
P7056 Insider’s Information 题目大意 给定 $m$ 个三元组，你需要给出一个序列满足其中的任意至少 $\lceil \frac{m}{2} \rceil$ 个三元组。 思路 定义每个三元组为 $[a_i,b_i,c_i]$，则满足的条件是 $b_i$ 处于 $a_i$ 与 $c_i$ 之间。 不难发现若仅计算这一个三元组对答案产生的贡献，则 $a_i$ 与 $c_i$ 是等价的，交换它们的位置不会影响贡献。 不难想到对所有点进行拓扑排序，确定 $b_i$ 一定在 $a_i$ 与 $c_i$ 后被填入。 所以分别连 $a_i$ 到 $b_i$ 的边及 $c_i$ 到 $b_i$ 的边，每个三元组中的 $b_i$ 入度每次加二。 然后进行拓扑排序，但在减去删去点的关联点入度时判断是否已经被减过（先遍历到了另外一端的端点），若未被减过，则将其入度减二，否则不减。 在拓扑排序后考虑按拓扑序填入答案，记 $ord_i$ 为拓扑序的第 $i$ 个数，计算其放在前端和后端分别能产生多少贡献，从两边往中间填充。 Code 12345678910111213141516...