题目理解

这是 BalticOI 2015 Tug of War 问题的解决方案。题目要求将 $2n$ 名选手分配到绳子的左右两边，满足位置约束且两队力量差不超过 $k$。

代码思路解析

1. 图论建模

将问题转化为二分图：

• 左边 $n$ 个点表示左边位置
• 右边 $n$ 个点表示右边位置
• 每个选手是一条连接 $(l_i, r_i+n)$ 的边，权值为力量 $s_i$

add(u, v + n, w), add(v + n, u, w);

2. 拓扑排序处理链

while (!q.empty()) {
    int u = q.front();
    // 处理度数为1的点
}

• 处理度数为1的节点（必须选择某条边）
• 这些边的选择是确定的，直接计入答案

3. 环检测与处理

剩余节点构成环：

for (int i = 1; i <= n * 2; i++)
    if (du[i] > 2) {
        cout << "NO\n";
        return 0;
    }

• 检查是否所有节点度数 ≤ 2（只能是环或链）
• 度数 > 2 说明无解

4. 环的两种选择

对每个环进行DFS，计算两种染色方案的差值：

dfs(i, i), cnt[abs(sum0 - sum1)]++, ans += min(sum0, sum1);

• sum0 和 sum1 表示环的两种染色方案的力量和
• 记录差值出现的次数
• 选择较小的方案加入基础答案

5. 可行性判断

使用 bitset 进行可行性背包：

dp[0] = 1;
for (int i = 1; i <= n * 40; i++)
    for (int j = 1; cnt[i]; j = min(j * 2, cnt[i]))
        cnt[i] -= j, dp |= (dp << (j * i));

• 二进制优化多重背包
• 检查是否存在差值在允许范围内

关键技巧

1. 图论转化

将位置约束转化为二分图匹配问题

2. 分离确定部分

通过拓扑排序处理必须选择的边

3. 环的二元选择

每个环只有两种可行的分配方案

4. 高效背包

使用 bitset 和二进制优化处理多重背包

复杂度分析

• 拓扑排序：$O(n)$
• 环处理：$O(n)$
• 多重背包：$O(\frac{n \cdot \text{maxW}}{\text{wordsize}})$
• 总复杂度：可接受

总结

这个解法是典型的图论+动态规划组合：

1. 图论建模：将问题转化为二分图
2. 拓扑分解：分离确定的选择
3. 环分析：处理剩余的二元选择
4. 背包判断：使用 bitset 高效检查可行性

体现了竞赛中问题转化和算法组合的高级技巧。