C++ 深度优先搜索解决[NOIP2009 提高组]最优贸易问题

C++ 代码实现：深度优先搜索解决最优贸易问题

这篇文章将介绍如何使用 C++ 的深度优先搜索 (DFS) 算法解决 [NOIP2009 提高组] 最优贸易问题。

问题描述

C 国有 n 个城市和 m 条道路，每条道路连接两个城市，可能是单向或双向通行。每个城市都有一种商品，在不同城市的价格可能不同。商人阿龙计划在 C 国旅游，他可以选择在某个城市买入商品，然后在另一个城市卖出赚取差价。阿龙最多进行一次这样的贸易，请问他最多能赚取多少旅费？

算法思路

我们可以将城市视为图中的节点，道路视为边，利用深度优先搜索算法 (DFS) 遍历所有可能的路径，并计算每条路径上的最大利润。

构建图： 使用邻接表存储图的结构，其中每个节点存储与其相邻的节点。2. 深度优先搜索： 从起点城市出发，递归地访问所有可达的城市。 * 在访问每个城市时，记录当前路径上的最大利润和最小购买价格。 * 如果当前城市的商品价格高于最小购买价格，则更新最大利润。 * 递归访问相邻城市，并将当前利润和最小购买价格传递给下一层递归。3. 返回最大利润： DFS 结束后，返回所有路径上的最大利润。

代码实现cpp#include #include

using namespace std;

const int MAXN = 100001;

vector graph[MAXN]; // 存储图的结构vector prices(MAXN); // 存储每个城市的水晶球价格vector visited(MAXN, 0); // 记录每个城市是否被访问过

int maxProfit = 0; // 最大旅费

void dfs(int curr, int profit, int minPrice) { visited[curr] = 1;

// 更新最大利润    maxProfit = max(maxProfit, profit);

// 遍历相邻城市    for (int next : graph[curr]) {        if (!visited[next]) {            // 计算利润            int newProfit = prices[next] - minPrice;            // 递归访问下一个城市            dfs(next, max(profit, newProfit), min(minPrice, prices[next]));        }    }

visited[curr] = 0; // 回溯}

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

// 输入城市商品价格    for (int i = 1; i <= n; i++) {        cin >> prices[i];    }

// 构建图    for (int i = 0; i < m; i++) {        int x, y, z;        cin >> x >> y >> z;        graph[x].push_back(y);        if (z == 2) {            graph[y].push_back(x);        }    }

// 从城市 1 开始 DFS    dfs(1, 0, prices[1]);

// 输出最大利润    cout << maxProfit << endl;

return 0;}

总结

本文介绍了使用 C++ 的深度优先搜索算法解决 NOIP2009 提高组中“最优贸易”问题的思路和代码实现。DFS 算法是解决图论问题的重要工具之一，希望本文能帮助您理解和掌握该算法在实际问题中的应用。