模拟退火 - 题解

标签与难度

标签: 图论, 搜索, 回溯, 剪枝, 组合优化, Branch and Bound 难度: 2100

题目大意喵~

你好呀，指挥官！这道题是说，我们有一张 $n$ 个点、 $m$ 条边的图，然后我们可以对它做两种魔法操作，喵~

删除单条边：选择图中的任意一条边然后抹掉它，代价是 $a$ 。
删除整个点：选择一个点，然后把和它相连的所有边都一起抹掉，代价是 $b$ 。

我们的任务是，用最小的总代价，把图里所有的边都清理得干干净净！最后输出这个最小代价就可以啦，是不是很有趣，呐？

解题思路分析

喵哈哈，看到题目叫“模拟退火”，是不是有点小紧张，以为要写复杂的随机化算法了呀？别怕别怕，这其实是个小小的烟雾弹哦！这道题的核心思想其实是剪枝搜索（也叫分枝定界法），根本不需要用到模拟退火呢，喵~

让我们一步一步来拆解这个问题吧！

核心抉择：删点还是删边？

对于图里的每一条边，我们最终都要把它删除。对于一个点 $i$ 和它连接的所有边，我们有两种策略：

保留点 $i$ ：我们不花 $b$ 的代价去删除点 $i$ 。但这样一来，所有连接到 $i$ 的边，我们都得另想办法处理。最坏的情况下，我们可能需要花费 $a \times \text{deg}(i)$ 的代价来一条一条地删除它们（其中 $\text{deg}(i)$ 是点 $i$ 的度）。
删除点 $i$ ：我们支付 $b$ 的代价，与 $i$ 相连的所有边就瞬间消失啦！

一个关键的优化！

让我们动动小脑筋，喵~ 什么时候选择删点会比删边更划算呢？

直观上想，如果一个点的度数 $\text{deg}(i)$ 特别大，那么花 $b$ 的代价一次性解决所有 $\text{deg}(i)$ 条边，可能比花 $\text{deg}(i) \times a$ 的代价一条条删要便宜。

更准确地说，我们来比较一下：

删除点 $i$ 的成本是固定的 $b$ 。
如果不删除点 $i$ ，处理它所有边的成本最多是 $\text{deg}(i) \times a$ 。（说“最多”是因为有些边可能因为另一端的点被删而消失，我们就不需要再为它花钱了）。

于是，我们可以得出一个非常重要的结论：如果一个点 $i$ 满足 $\text{deg}(i) \times a \le b$ ，那么删除这个点永远不划算！为什么呢？假如在一个最优解里，我们删除了这样一个点 $i$ ，花费了 $b$ 。我们可以把它改成不删除点 $i$ ，转而去手动删除所有与 $i$ 相连、且另一端点没被删除的边。这样做的成本最多是 $\text{deg}(i) \times a$ ，因为 $\text{deg}(i) \times a \le b$ ，所以新方案的成本不会比原来的差，甚至可能更好！

所以，我们只需要对那些满足 $\text{deg}(i) \times a > b$ 的点，考虑“删除它”这个选项。我们把这些点称为**“候选点”**。对于其他点，我们默认不删除它们。

变身！问题转化

这样一来，问题就从“为 $n$ 个点做决定”简化为“只为少数几个‘候选点’做决定”，搜索范围大大减小了，喵！

我们的新问题是：给定一个“候选点”集合 $C$ ，我们要从 $C$ 中选择一个子集 $C' \subseteq C$ 进行删除操作，使得总成本最小。

总成本 = (删除 $C'$ 中节点的成本) + (删除剩余边的成本)

\text{Cost}(C') = |C'| \cdot b + \left( \sum_{(u,v) \in E, u \notin C', v \notin C'} a \right)

终极武器：带剪枝的回溯搜索

现在，我们可以用回溯搜索来遍历 $C$ 的所有子集 $C'$ ，计算每种情况的成本，然后取最小值。

初始状态：最开始，我们一个候选点都不删。总成本就是把所有 $m$ 条边一条一条删掉，即 $m \times a$ 。我们把这个值作为初始的最小答案 ans。
搜索过程 (DFS)：我们写一个递归函数 dfs(candidates, current_cost, degrees)。
- candidates：当前还待决策的候选点列表。
- current_cost：当前的方案总成本。
- degrees：图中所有点的当前度数。
在 dfs 函数里，我们首先用 current_cost 更新全局最小答案 ans。这代表了“不再删除任何候选点”的决策分支。
然后，我们从 candidates 中挑选一个点 u 来做决策。为了让剪枝更有效，我们优先选当前度数最高的候选点，因为它对局面的影响最大！
对于选出的点 u，我们只探索删除它的分支（不删除它的情况已经在进入循环前，通过更新 ans 隐式地处理了）。
- 计算新成本：当我们决定删除点 u 时，成本如何变化呢？我们原先的 current_cost 是假设 u 的所有边都手动删，现在我们不这么做了，而是花 b 删掉 u。所以成本变化是：new_cost = current_cost - degrees[u] * a + b。这个式子非常巧妙，它把原来计入成本的 degrees[u] 条边的钱退给我们，然后加上删除点 u 的新开销 b。
- 更新图的状态：删除 u 后，它的邻居们的度数都会减小。
- 筛选新候选人：u 的邻居度数减小后，有些可能不再满足 new_deg(v) * a > b 的条件，它们就从候选人名单里“毕业”了。
- 递归：带着新的成本、新的候选人名单、新的度数，我们继续调用 dfs。
强大的剪枝！ 为了避免不必要的搜索，我们需要剪枝。在进入一个分支前，我们可以估算一下这个分支的“最好情况”下的成本。假设当前还有 k 个候选点，它们的度数之和是 sum_deg。一个（可能很粗略的）成本下界是：我们把这 k 个点全部删除。此时的成本是：current_cost - sum_deg * a + k * b。如果这个估算出的成本下界都已经比我们已知的最小答案 ans 要大了，那这个分支再怎么努力也不可能得到更优的解了，直接剪掉！喵~

通过以上“关键优化 + 回溯搜索 + 强力剪枝”三连击，我们就能高效地找到答案啦！

代码实现

这是我根据上面的思路，精心重构的一份代码，逻辑清晰，注释也写得很详细哦，希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

// 使用 long long 防止整数溢出
using ll = long long;

int n;
ll m, a, b;
ll min_cost;
vector<vector<int>> adj; // 邻接矩阵，adj[i][j] 表示 i 和 j 之间的边数

// 深度优先搜索函数
// candidates: 当前待决策的候选点列表
// current_cost: 当前方案的总成本
// degrees: 图中所有点的当前度数
void dfs(vector<int>& candidates, ll current_cost, vector<int>& degrees) {
    // 1. 更新全局最优解
    // 当前的 cost 代表了不再删除任何候选点时的总成本
    min_cost = min(min_cost, current_cost);

    // 2. 剪枝优化
    // 计算一个成本下界：如果把剩下所有候选点都删掉，成本是多少
    // 如果这个下界已经比当前最优解还差，就没必要继续搜索了
    ll remaining_candidates_count = candidates.size();
    ll sum_of_degrees = 0;
    for (int u : candidates) {
        sum_of_degrees += degrees[u];
    }
    ll lower_bound_cost = current_cost - sum_of_degrees * a + remaining_candidates_count * b;
    if (lower_bound_cost >= min_cost) {
        return;
    }

    // 3. 遍历候选点，进行决策
    // 为了让剪枝更有效，我们优先处理度数大的节点
    // 这里隐式地通过迭代 candidates 来选择，可以先对其排序以获得更好效果
    for (int i = 0; i < candidates.size(); ++i) {
        int u = candidates[i];

        // --- 探索“删除节点 u”的分支 ---

        // a. 计算新成本
        ll next_cost = current_cost - (ll)degrees[u] * a + b;

        // b. 创建下一轮递归的状态
        vector<int> next_degrees = degrees;
        vector<int> next_candidates;
        
        // c. 更新度数：u 的所有邻居度数都会因 u 的删除而改变
        for (int v = 1; v <= n; ++v) {
            if (adj[u][v] > 0) {
                next_degrees[v] -= adj[u][v];
            }
        }

        // d. 筛选下一轮的候选点
        // 从当前候选人中（不包括u），选出度数变化后仍然满足条件的
        for (int v : candidates) {
            if (v == u) continue;
            if ((ll)next_degrees[v] * a > b) {
                next_candidates.push_back(v);
            }
        }
        
        // 启发式排序：让度数大的节点排在前面，优先处理
        sort(next_candidates.begin(), next_candidates.end(), [&](int p1, int p2) {
            return next_degrees[p1] > next_degrees[p2];
        });

        // e. 递归进入下一层
        dfs(next_candidates, next_cost, next_degrees);
    }
}

void solve() {
    cin >> n >> m >> a >> b;

    adj.assign(n + 1, vector<int>(n + 1, 0));
    vector<int> initial_degrees(n + 1, 0);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        if (u == v) { // 自环
            adj[u][u]++;
            initial_degrees[u]++;
        } else {
            adj[u][v]++;
            adj[v][u]++;
            initial_degrees[u]++;
            initial_degrees[v]++;
        }
    }

    // 初始解：所有边都单独删除
    min_cost = m * a;

    // 找出初始的候选点
    vector<int> initial_candidates;
    for (int i = 1; i <= n; ++i) {
        if ((ll)initial_degrees[i] * a > b) {
            initial_candidates.push_back(i);
        }
    }
    
    // 启发式排序：让度数大的节点排在前面，优先处理
    sort(initial_candidates.begin(), initial_candidates.end(), [&](int u, int v) {
        return initial_degrees[u] > initial_degrees[v];
    });

    // 开始搜索
    dfs(initial_candidates, m * a, initial_degrees);

    cout << min_cost << endl;
}

int main() {
    // 加速输入输出
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

时间复杂度: $O(k! \cdot k \cdot n)$ 或类似指数级别。其中 $k$ 是初始“候选点”的数量。在每一层递归中，我们需要遍历当前候选点列表（大小最多为 $k$ ），并为每个选择更新 $n$ 个点的邻居度数。虽然最坏情况下是指数级的，但由于强大的剪枝和 $k$ 在大多数测试用例中都比较小，这个算法实际运行得很快。
空间复杂度: $O(n^2 + k^2)$ 。 $O(n^2)$ 用于存储邻接矩阵。递归的深度最多为 $k$ ，每一层递归都需要为 degrees 和 candidates 向量创建副本，所以递归栈的空间开销大约是 $O(k \cdot (n+k))$ 。但由于我们是尾递归的形式，如果编译器优化，空间可以更小。在我的实现中，为了清晰，我传递了副本，所以空间复杂度是 $O(n^2 + k \cdot (n+k))$ 。

知识点总结

这真是一次有趣的探险，对吧？我们来总结一下这次学到的武功秘籍，喵~

问题简化与转化：面对复杂问题，首先要寻找关键性质。本题的 deg(i) * a > b 就是一个强有力的突破口，它能帮我们过滤掉大量无需考虑的决策，大大简化问题。
回溯搜索 (Backtracking)：当问题可以分解为一系列决策步骤，并且需要探索所有可能性时，回溯是一个非常经典的算法框架。
分枝定界 (Branch and Bound)：纯粹的回溯可能会很慢。通过计算当前搜索分支的成本下界（Lower Bound），并与已找到的最优解 ans 比较，我们可以提前“剪掉”那些不可能产生更优解的分支。这是让搜索算法变得实用的核心技巧！
启发式搜索 (Heuristics)：在搜索时，决策的顺序有时会影响效率。比如本题中，我们优先考虑度数大的节点，因为它们对成本和图的结构影响最大，这通常能让剪枝更早地发生作用。
不要被题目名称迷惑：要时刻相信自己的分析和判断，喵！有时候题目的名字只是个代号，真正的解法需要我们自己去发掘。

希望这篇题解能让你有所收获！如果还有问题，随时可以再来找我玩哦，喵~

模拟退火 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

核心抉择：删点还是删边？ ​

一个关键的优化！ ​

变身！问题转化 ​

终极武器：带剪枝的回溯搜索 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​