题目概述

Bajtazar 国王要将王国分成两半，给两个儿子。王国有 $n$ 个城市（$n$ 为偶数），通过道路连接。要求：

• 每半有 $n/2$ 个城市
• 连接两半的道路数量（需要建哨所）尽可能少
• 城市 1 必须在输出的那一半中

---

问题分析

关键点

• $n \leq 26$，规模较小
• 需要将城市分成两个大小相等的集合
• 最小化两个集合之间的边数（图论中的最小割问题）
• 由于 $n$ 是偶数且不大，可以暴力枚举所有划分方案

问题转化

这实际上是图论的平衡最小割问题：

• 给定一个无向图
• 将顶点集划分为两个大小相等的子集
• 使得两个子集之间的边数最少

---

算法思路

暴力搜索

由于 $n \leq 26$，$n/2 = 13$，需要从 $n$ 个城市中选择 $n/2$ 个城市（包含城市1）。

组合数计算：从剩下的 $n-1$ 个城市中选择 $n/2-1$ 个城市：

• 当 $n=26$ 时，$C_{25}^{12} \approx 5.2 \times 10^6$，可以接受

数据结构

使用 bitset 高效表示：

• e[i]：城市 $i$ 的邻接表（哪些城市与之相连）
• bk：当前选择的城市集合
• ans：最优的城市集合

算法步骤

1. 读入图：建立邻接矩阵的 bitset 表示
2. DFS 枚举：枚举所有包含城市1的大小为 $n/2$ 的子集
3. 计算割边数：对于每个子集，计算与另一子集之间的边数
4. 记录最优解：保持割边数最少的划分方案

---

算法详解

核心代码解析

数据结构初始化

bitset<N> e[N], bk, ans;  // 邻接表、当前选择、最优选择

DFS 搜索

void dfs(int x, int cnt) {
    if (cnt == n / 2) {  // 已选择n/2个城市
        int num = 0;
        
        // 计算割边数：对于不在选择集中的城市，统计与选择集的边数
        for (int i = 1; i <= n; ++i) {
            if (bk[i] == 0) {
                num += (e[i] & bk).count();
            }
        }
        
        if (num < ansx)  // 更新最优解
            ans = bk, ansx = num;
        return;
    }
    
    if (x > n) return;
    
    // 选择城市x
    bk[x] = 1;
    dfs(x + 1, cnt + 1);
    
    // 不选择城市x（但要保证城市1始终被选择）
    bk[x] = 0;
    dfs(x + 1, cnt);
}

主函数

int main() {
    cin >> n >> m;
    
    // 构建邻接表
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        e[u][v] = 1, e[v][u] = 1;
    }
    
    // 城市1必须被选择
    bk[1] = 1;
    dfs(2, 1);  // 从城市2开始搜索，已选择1个城市
    
    // 输出结果
    for (int i = 1; i <= n; ++i)
        if (ans[i])
            cout << i << ' ';
    
    return 0;
}

割边数计算技巧

对于每个划分方案，割边数可以这样计算：

• 遍历所有不在选择集中的城市
• 对每个这样的城市，统计它与选择集中城市的连接数
• 使用 bitset 的按位与操作 (e[i] & bk).count() 高效计算

---

样例解析

样例输入

6 8
1 2
1 6
2 3
2 5
2 6
3 4
4 5
5 6

图结构（完全图的一部分）：

1 - 2 - 3
| \ |   |
6 - 5 - 4

最优解分析

输出：1 2 6

划分：

• 集合 A: {1, 2, 6}
• 集合 B: {3, 4, 5}

割边：

• 1-? （都在A内）
• 2-3, 2-5
• 6-5
• 3-4, 4-5 （都在B内）

总共 3 条割边：2-3, 2-5, 6-5

验证其他划分

• 如果选择 {1, 2, 3}，割边为：1-6, 2-5, 2-6, 3-4, 3-5（5条）
• 如果选择 {1, 5, 6}，割边为：1-2, 2-3, 2-6, 4-5, 5-2（5条）

可见 {1, 2, 6} 确实是最优的。

---

复杂度分析

时间复杂度

• 组合数：$C_{n-1}^{n/2-1}$
• 每个组合的计算：$O(n)$（使用 bitset 优化）
• 总复杂度：$O(n \times C_{n-1}^{n/2-1})$

对于 $n=26$：$25 \times C_{25}^{12} \approx 1.3 \times 10^8$ 次操作，可以接受。

空间复杂度

• $O(n^2)$ 存储邻接矩阵
• 在 $n \leq 26$ 时很小

---

算法优化

剪枝策略

虽然本题数据规模不需要剪枝，但可以进一步优化：

• 如果当前割边数已经超过已知最优解，可以提前返回
• 使用位运算加速集合操作

bitset 的优势

• 内存紧凑：每个 bitset<N> 只占 $\lceil N/8 \rceil$ 字节
• 操作高效：按位与、计数等操作都是 $O(1)$ 或 $O(N/机器字长)$

---

总结

这道题展示了暴力搜索在数据规模较小时的实用性：

1. 问题识别：识别出这是平衡最小割问题
2. 规模分析：$n \leq 26$ 允许组合枚举
3. 高效实现：使用 bitset 加速集合操作
4. 约束处理：确保城市1在输出集合中

这种"小规模暴力 + 位运算优化"的策略在编程竞赛中非常常见，特别是在 $n \leq 20-30$ 的情况下。