C++ 实现 Z 国军队驻扎问题求解

以下是使用 C++ 实现上述问题的代码： ```cpp #include <iostream> #include <vector> #include <cstring> #include <algorithm> #define INF 0x3f3f3f3f using namespace std; const int MAXN = 100005; // 存储图的邻接表 vector<int> adj[MAXN]; // 存储每个城市的花费 int p[MAXN]; // 动态规划数组，dp[i][0] 表示第 i 个城市不驻扎军队的最小花费，dp[i][1] 表示第 i 个城市驻扎军队的最小花费 int dp[MAXN][2]; // 标记城市是否有驻扎要求 int req[MAXN]; // 深度优先搜索函数，用于计算最小花费 void dfs(int u, int fa) { // 初始化当前城市不驻扎军队和驻扎军队的花费 dp[u][0] = 0; dp[u][1] = p[u]; for (int v : adj[u]) { if (v == fa) continue; dfs(v, u); // 如果当前城市不驻扎军队，那么相邻城市必须驻扎军队 dp[u][0] += dp[v][1]; // 如果当前城市驻扎军队，相邻城市可以驻扎也可以不驻扎，取最小值 dp[u][1] += min(dp[v][0], dp[v][1]); } // 如果当前城市有不驻扎军队的要求，将驻扎军队的花费设为无穷大 if (req[u] == 0) dp[u][1] = INF; // 如果当前城市有驻扎军队的要求，将不驻扎军队的花费设为无穷大 if (req[u] == 1) dp[u][0] = INF; } int main() { int n, m; string type; cin >> n >> m >> type; // 输入每个城市的花费 for (int i = 1; i <= n; i++) { cin >> p[i]; } // 构建图 for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } // 处理每个要求 for (int i = 0; i < m; i++) { int a, x, b, y; cin >> a >> x >> b >> y; // 初始化要求标记数组 memset(req, -1, sizeof(req)); req[a] = x; req[b] = y; // 进行深度优先搜索 dfs(1, 0); // 计算最小花费 int ans = min(dp[1][0], dp[1][1]); // 如果最小花费为无穷大，说明无法满足要求 if (ans >= INF) ans = -1; cout << ans << endl; } return 0; } ``` ### 代码解释： 1. **图的构建**：使用邻接表 `adj` 存储图的结构，通过 `n - 1` 条边构建无向图。 2. **动态规划数组**：`dp[i][0]` 表示第 `i` 个城市不驻扎军队的最小花费，`dp[i][1]` 表示第 `i` 个城市驻扎军队的最小花费。 3. **深度优先搜索**：在 `dfs` 函数中，递归计算每个城市不驻扎和驻扎军队的最小花费。 4. **处理要求**：对于每个要求，使用 `req` 数组标记城市是否有驻扎要求，然后重新进行深度优先搜索计算最小花费。 5. **输出结果**：如果最小花费为无穷大，说明无法满足要求，输出 `-1`；否则输出最小花费。 ######[AI问答 | 919点数解答 | 2026-05-30 20:25:49]