[BalticOI 2015] Tug of War

题意

拔河（Tug of War）在 Byteland 是十分受欢迎的运动。规则十分简单：两队以相反方向拉绳子。一年一度的 Byteland 拔河比赛将要进行，并且许多选手都报名参加了。作为公平竞赛专员，你的工作是把选手们划分为两个队伍，使得这个比赛能够进行很长时间。

由于一共 \(2n\) 名选手报名参赛，所以一个队有 \(n\) 名队员。一根绳上左右两边各有 \(n\) 个点。Byteland 的拔河精英们都很挑剔，每个参赛选手在左右两边都有一个他们想要站的位置。此外，你知道每一个参赛选手的力量值。

组织者现在问你如下的问题：给定一个整数 \(k\)，能否分出两个队，这两个队各有 \(n\) 名选手，并且他们站在他们想站的位置（当然不能有两名或以上选手站在同一位置），双方力量和之差不超过 \(k\)？

题解

考试的时候落入网络流的漩涡，然后就被薄纱了。
考虑建图，我们由 \(l_i\) 向 \(r_{i+n}\) 连一条权值为 \(s_i\) 的无向边，等价于选择将这条边分配给左右两个点。
一个是正权值，一个负权值，显然我们希望点权之和的绝对值最小。
注意到我们有 \(2n\) 条边和 \(2n\) 个点，显然每个人都有位置的方案是一颗基环树森林。
基环树是一个环加上一些树，显然对于树的部分边的分配已经确定。
对于环我们有逆时针和顺时针的方式分配，且两种分配方式的权值和互为相反数。
由于树的权值和是一个定值，我们显然就应该确定每一个环的正负来使得总权值在限制之内。
注意到 \(s_i\) 的值并不大，所以我们使用 \(01\) 背包来解决这个存在性问题。
这个 \(01\) 背包显然可以使用 bitset 优化，设总权值为 \(na\)，这时候复杂度为 \(O(\frac{n^2a}{w})\) ，实现精细可通过。
考虑优化，注意到不同的值最多只有 \(\sqrt{na}\) 个，所以我们将许多值相同的环压在一起，然后做多重背包。
然后使用二进制优化即可，设 \(na\) 为 \(T\)，时间复杂度 \(O(\frac{T^{\frac{3}{2}}logT}{w})\)。code