C++ 实现无向图中三个顶点最大值计算

C++ 实现无向图中三个顶点最大值计算

给定一个有 n 个顶点 m 条边的简单无向图，第 i 个顶点的点权是 v_i。需要找到三个相异的顶点 (a, b, c)，满足 a 和 b 相邻，b 和 c 相邻。求 v_a × v_c - v_b 的最大值。保证有解。

C++ 代码

以下是使用 C++ 语言编写的代码，根据给定的简单无向图，找到满足条件的三个相异的顶点，并计算最大值：

#include <iostream>
#include <vector>

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<int> vertexWeights(n);
    for (int i = 0; i < n; i++) {
        std::cin >> vertexWeights[i];
    }

    std::vector<std::vector<int>> adjacencyList(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;
        adjacencyList[u - 1].push_back(v - 1);
        adjacencyList[v - 1].push_back(u - 1);
    }

    long long maxResult = 0;

    for (int a = 0; a < n; a++) {
        for (int b : adjacencyList[a]) {
            for (int c : adjacencyList[b]) {
                if (c == a) {
                    continue;
                }
                long long result = 1LL * vertexWeights[a] * vertexWeights[c] - vertexWeights[b];
                maxResult = std::max(maxResult, result);
            }
        }
    }

    std::cout << maxResult << std::endl;

    return 0;
}

此代码假设输入是有效的，并且没有对输入进行错误检查。在实际应用中，你可能需要添加错误处理和边界情况的检查。希望这可以帮到你！