厄神降臨之路 - 题解

标签与难度

标签: 图论, 深度优先搜索, DFS, 回溯, 剪枝, 暴力枚举难度: 2100

题目大意喵~

一位名叫键山雏的厄神大人，给了我们一张由 $n$ 个点组成的简单无向图，喵~ 这张图有点特别哦！

每个点 $i$ 都有一个自己的“点权” $a_i$ 。
连接点 $i$ 和点 $j$ 的每条边，也有一个“边权” $e_{ij}$ 。
我们被要求在这张图里找到一个环。
一个“环”的“花费”被定义为：环上所有点权之和与所有边权之和的乘积。
我们的任务，就是找到那个花费最小的环，把最小花费告诉厄神大人。如果图里一个环都找不到，就要报告 -1，不然厄运就要降临啦！

简单来说，就是在一个点和边都有权重的图里，找一个环，使得 (环上点权总和) * (环上边权总和) 这个值最小，呐。

解题思路分析

喵~ 各位寻路的小伙伴们，这道题是要我们在一张复杂的地图上找到一条最“划算”的环路呢！看到题目要求“最小花费”，而且花费的计算方式是 (点权和) * (边权和)，我们就要开始动动我们的小脑袋瓜啦。

首先，注意到题目给出的点数 $n$ 不会很大（从参考代码来看，大约在25以内）。这个小小的 $n$ 是一个非常重要的提示哦！它在暗示我们，一个时间复杂度比较高、甚至是指数级的算法，只要实现得当，也是可以通过的。

那么，要找遍所有的环，最自然的方法是什么呢？当然是**深度优先搜索（DFS）**啦！我们可以把图上的每一个点都当作一个潜在的环的起点，然后从这个起点出发，去探索所有能走回起点的路径，也就是环路。

让我们来一步步构思这个搜索过程，喵~

枚举起点: 一个环可以从任何一个点开始。所以，我们可以写一个循环，依次把每个点 i (从 0到n-1) 当作我们寻找的环的起点 startNode。
DFS探索路径: 对于每一个选定的 startNode，我们启动一次深度优先搜索。我们需要一个递归函数，比如 dfs(currentNode, pathNodeSum, pathEdgeSum)，它需要携带以下信息：
- currentNode: 当前我们走到了哪个节点。
- pathNodeSum: 从 startNode 走到 currentNode 的这条路径上，所有节点的点权之和。
- pathEdgeSum: 从 startNode 走到 currentNode 的这条路径上，所有边的边权之和。
避免重复访问: 为了保证我们找到的是“简单环”（即除了起点和终点重合外，路径上没有重复节点），我们需要一个 visited 数组来记录在当前这次DFS中，哪些点已经被访问过了。出发前，我们将 startNode 标记为已访问。
找到环啦！: 在 dfs 函数中，当我们从 currentNode 准备走到下一个邻居节点 nextNode 时：
- 如果 nextNode 就是我们的 startNode: 哇！我们成功地从起点出发，绕了一圈又回来了！这就构成了一个环。这时，我们就可以计算这个环的总花费了。
  - 环的点权和就是当前的 pathNodeSum。
  - 环的边权和是 pathEdgeSum 加上最后这条连接 currentNode 和 startNode 的边的权重。
  - 所以花费是 pathNodeSum * (pathEdgeSum + edge_weight(currentNode, startNode))。
  - 我们用这个花费去更新我们的全局最小花费 minCost。
- 如果 nextNode 还没有被访问过: 说明我们可以继续延伸这条路径。我们把 nextNode 标记为已访问，然后带着更新后的点权和与边权和，递归地调用 dfs(nextNode, ...)。探索完之后，记得要回溯，也就是把 nextNode 的 visited 状态恢复成未访问，这样才不会影响其他路径的搜索哦！
聪明的剪枝喵！: 如果我们只是这样傻乎乎地搜索，可能会因为路径太多而超时。这里有一个非常重要的优化，叫做剪枝（Pruning）。在我们的搜索过程中，pathNodeSum 和 pathEdgeSum 都是单调递增的。如果我们发现，在当前路径上，pathNodeSum * pathEdgeSum 这个中间结果就已经大于等于我们已经找到的最小花费 minCost 了，那还有必要继续往下走吗？当然没有啦！因为继续走下去，点权和与边权和只会更大，最终的花费也必然会更大。所以，我们就可以像小猫一样，果断地掉头，不再探索这条没有前途的路径了。这个小技巧可以砍掉大量的无效搜索，让我们的程序跑得飞快！

总结一下我们的策略：

外层循环遍历每个节点作为环的起点 startNode。
对每个 startNode，进行一次带剪枝的深度优先搜索。
DFS函数负责探索所有从 startNode 出发的简单路径。
当路径能回到 startNode 时，计算环的花费并更新全局最小值。
在DFS过程中，如果当前部分路径的 点权和 * 边权和 已超过已知最小花费，则停止深入。

最后，如果搜索结束后，minCost 还是我们设定的初始极大值，那就说明图中没有环，我们输出 -1。否则，就输出找到的 minCost。这样，就能完美解决问题啦，喵~

代码实现

这是我根据上面的思路，精心重构的一份代码~ 注释很详细，希望能帮到你哟！

cpp

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

// 使用 long long 来防止花费计算时溢出
using ll = long long;
const ll INF = 1e18; // 一个足够大的数表示无穷大

int n; // 图的节点数
std::vector<int> a; // 存储每个点的点权
std::vector<std::vector<int>> g; // 邻接矩阵存储边权，g[i][j]=0表示无边

ll min_cost = INF; // 全局变量，记录找到的最小花费
std::vector<bool> visited; // 标记节点在当前DFS路径中是否被访问
int start_node; // 当前正在寻找的环的起点

// 深度优先搜索函数
// u: 当前所在的节点
// path_node_sum: 从起点到当前节点u的路径上的点权之和
// path_edge_sum: 从起点到当前节点u的路径上的边权之和
void dfs(int u, ll path_node_sum, ll path_edge_sum) {
    // 剪枝优化！如果当前的部分花费已经不优，就没必要继续搜下去了
    if (path_node_sum * path_edge_sum >= min_cost) {
        return;
    }

    // 遍历所有与u相连的节点v
    for (int v = 0; v < n; ++v) {
        // g[u][v] > 0 表示u和v之间有边
        if (g[u][v] > 0) {
            // Case 1: 找到了一个环！
            // v是起点，并且路径长度大于1（即环至少包含两个节点和两条边）
            // 注意：如果允许两个点构成的环，这里的判断是 `v == start_node` 即可。
            // 题意中环的定义为"不经过一条边一次以上"，从一个点出发回到这个点，
            // 意味着至少需要两个点和两条边（A->B, B->A）。
            if (v == start_node && path_edge_sum > 0) {
                ll current_cost = path_node_sum * (path_edge_sum + g[u][v]);
                min_cost = std::min(min_cost, current_cost);
                continue; // 继续寻找其他可能的环
            }
            
            // Case 2: 探索未访问过的节点
            if (!visited[v]) {
                visited[v] = true; // 标记为已访问
                // 递归进入下一层搜索
                dfs(v, path_node_sum + a[v], path_edge_sum + g[u][v]);
                visited[v] = false; // 回溯，恢复状态
            }
        }
    }
}


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

    std::cin >> n;

    // 初始化数据结构
    a.resize(n);
    g.assign(n, std::vector<int>(n));
    visited.resize(n);

    // 读入点权
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 读入边权（邻接矩阵）
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cin >> g[i][j];
        }
    }

    // 枚举每个节点作为环的起点
    for (int i = 0; i < n; ++i) {
        start_node = i;
        std::fill(visited.begin(), visited.end(), false); // 重置visited数组
        visited[start_node] = true; // 标记起点
        // 从起点开始DFS，初始边权和为0
        dfs(start_node, a[start_node], 0);
    }

    // 如果min_cost没有被更新过，说明没有找到环
    if (min_cost == INF) {
        std::cout << -1 << std::endl;
    } else {
        std::cout << min_cost << std::endl;
    }

    return 0;
}

复杂度分析

时间复杂度: $O(N! \cdot N)$ 在最坏情况下。这是一个比较粗略的上界。精确分析很复杂，因为搜索过程是在一个图上进行的，并且有剪枝。在没有剪枝的朴素DFS中，我们需要寻找所有简单路径。从一个固定起点出发，长度为 $k$ 的简单路径数量级约为 $(N-1) \cdot (N-2) \cdot \ldots \cdot (N-k+1)$ 。我们需要对所有可能的路径长度和所有起点进行搜索，所以复杂度是指数级的，与 $N!$ 相关。幸运的是，题目给定的 $N$ 很小，而且剪枝优化能显著减少实际的搜索量，使得算法在时限内能够完成，喵~
空间复杂度: $O(N)$ 我们主要使用了 visited 数组来记录访问状态，其大小为 $O(N)$ 。此外，DFS的递归调用会占用调用栈空间，递归的最大深度为 $N$ ，所以栈空间也是 $O(N)$ 。因此，总的空间复杂度是 $O(N)$ 的说。

知识点总结

图的表示: 这道题使用了邻接矩阵来表示图，对于点数较少的稠密图来说，这是一个简单直接的选择。
深度优先搜索 (DFS) 与回溯: 寻找图中所有路径或环的经典方法。核心在于递归探索与状态恢复（回溯）。
剪枝优化: 这是让暴力搜索算法变得可行的关键技巧。通过设定一个界限（本题中是已找到的 min_cost），提前终止不可能产生更优解的搜索分支，大大提高了效率。
NP-Hard 问题的思路: 寻找最小环（尤其是有特殊代价函数的环）问题通常是NP-Hard的，比如旅行商问题（TSP）的变种。当看到数据范围很小（如 $N \le 25$ ）时，就应该联想到这可能是在提示我们使用指数级的算法，比如状态压缩DP或者带剪枝的暴力搜索。

希望这篇题解能帮到你，祝你解题愉快，不再被厄运缠身，喵~！

厄神降臨之路 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​