[蓝桥杯]植树

植树

题目描述

小明和朋友们一起去郊外植树，他们带了一些在自己实验室精心研究出的小树苗。

小明和朋友们一共有 nn 个人，他们经过精心挑选，在一块空地上每个人挑选了一个适合植树的位置，总共 nn 个。他们准备把自己带的树苗都植下去。

然而，他们遇到了一个困难：有的树苗比较大，而有的位置挨太近，导致两棵树植下去后会撞在一起。

他们将树看成一个圆，圆心在他们找的位置上。如果两棵树对应的圆相交，这两棵树就不适合同时植下（相切不受影响），称为两棵树冲突。

小明和朋友们决定先合计合计，只将其中的一部分树植下去，保证没有互相冲突的树。他们同时希望这些树所能覆盖的面积和（圆面积和）最大。

输入描述

输入的第一行包含一个整数 nn ，表示人数，即准备植树的位置数。

接下来 nn 行，每行三个整数 x, y, rx, y, r，表示一棵树在空地上的横、纵坐标和半径。

其中，1≤n≤30，0≤x,y≤1000，1≤r≤10001≤n≤30，0≤x,y≤1000，1≤r≤1000。

输出描述

输出一行包含一个整数，表示在不冲突下可以植树的面积和。由于每棵树的面积都是圆周率的整数倍，请输出答案除以圆周率后的值（应当是一个整数）。

输入输出样例

示例

输入

6
1 1 2
1 4 2
1 7 2
4 1 2
4 4 2
4 7 2

输出

12

运行限制

• 最大运行时间：3s
• 最大运行内存: 512M

总通过次数: 524  |  总提交次数: 785  |  通过率: 66.8%

难度: 困难   标签: 2020, 省模拟赛, 搜索

算法思路

本问题需要选择一组互不冲突的树（圆不相交），最大化总覆盖面积（半径平方和）。由于树的数量 n ≤ 30，可以采用深度优先搜索（DFS）配合优化策略：

1. ​​冲突检测​​：两棵树冲突的条件是圆心距² < (r₁ + r₂)²（严格小于，相切不算冲突）
2. ​​连通分量分解​​：将树按冲突关系划分为多个独立子集（分量内树可能冲突，分量间树绝对不冲突）
3. ​​DFS搜索​​：对每个连通分量独立搜索最优解
4. ​​剪枝优化​​：
   • 按半径降序排序（优先选择大半径树）
   • 后缀和剪枝（当前和 + 剩余树最大可能和 ≤ 当前最大值时剪枝）
5. ​​状态压缩​​：对小型分量（≤15 节点）使用位运算 DP 加速

算法步骤

1. ​​输入处理​​：读取树的数量和每棵树的坐标半径
2. ​​按半径降序排序​​：确保优先处理大半径树
3. ​​构建冲突图​​：
   • 计算任意两棵树圆心距²
   • 若圆心距² < (rᵢ + rⱼ)² 则标记冲突
4. ​​分解连通分量​​：
   • 用 BFS/DFS 将树划分为冲突连通的子集
   • 不同分量独立处理
5. ​​分量求解​​：
   • ​​小型分量（≤15）​​：状态压缩 DP
   • ​​大型分量​​：DFS + 后缀和剪枝
6. ​​结果合并​​：累加各分量最优解

算法演示

代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <unordered_map>
using namespace std;struct Tree {int x, y, r, id;
};// 计算圆心距平方（避免浮点误差）
long long distSq(const Tree& a, const Tree& b) {long long dx = a.x - b.x;long long dy = a.y - b.y;return dx*dx + dy*dy;
}// 冲突检测：圆心距² < (r1+r2)²
bool isConflict(const Tree& a, const Tree& b) {long long rSum = (long long)a.r + b.r;return distSq(a, b) < rSum * rSum;
}// 连通分量分解
vector<vector<int>> findComponents(vector<vector<bool>>& conflict) {int n = conflict.size();vector<bool> visited(n, false);vector<vector<int>> components;for (int i = 0; i < n; ++i) {if (visited[i]) continue;queue<int> q;vector<int> comp;q.push(i);visited[i] = true;while (!q.empty()) {int u = q.front();q.pop();comp.push_back(u);for (int v = 0; v < n; ++v) {if (conflict[u][v] && !visited[v]) {visited[v] = true;q.push(v);}}}components.push_back(comp);}return components;
}// 状态压缩DP（处理小规模分量）
int dpComp(const vector<Tree>& trees, const vector<vector<bool>>& compConflict) {int n = trees.size();if (n == 0) return 0;vector<int> dp(1 << n, 0);int best = 0;for (int mask = 1; mask < (1 << n); ++mask) {bool valid = true;int sumSq = 0;for (int i = 0; i < n && valid; ++i) {if (!(mask & (1 << i))) continue;sumSq += trees[i].r * trees[i].r;for (int j = i + 1; j < n; ++j) {if ((mask & (1 << j)) && compConflict[i][j]) {valid = false;break;}}}if (valid) {dp[mask] = sumSq;best = max(best, sumSq);} else {// 状态转移：枚举子集优化dp[mask] = 0;for (int submask = mask; submask; submask = (submask - 1) & mask) {dp[mask] = max(dp[mask], dp[submask]);}}}return best;
}// DFS + 剪枝（处理大规模分量）
void dfsComp(const vector<Tree>& trees, const vector<vector<bool>>& compConflict,vector<bool>& selected, int index, int currentSum, int& bestSum, const vector<int>& suffix) {if (index == trees.size()) {bestSum = max(bestSum, currentSum);return;}// 剪枝：当前和 + 剩余最大可能和 ≤ 最优解if (currentSum + suffix[index] <= bestSum) return;// 不选当前树dfsComp(trees, compConflict, selected, index + 1, currentSum, bestSum, suffix);// 检查与已选树是否冲突bool noConflict = true;for (int i = 0; i < index; ++i) {if (selected[i] && compConflict[index][i]) {noConflict = false;break;}}// 选当前树（无冲突时）if (noConflict) {selected[index] = true;int newSum = currentSum + trees[index].r * trees[index].r;dfsComp(trees, compConflict, selected, index + 1, newSum, bestSum, suffix);selected[index] = false;}
}int main() {int n;cin >> n;vector<Tree> trees(n);for (int i = 0; i < n; ++i) {cin >> trees[i].x >> trees[i].y >> trees[i].r;trees[i].id = i;}// 按半径降序排序（优化剪枝）sort(trees.begin(), trees.end(), [](const Tree& a, const Tree& b) {return a.r > b.r;});// 构建冲突矩阵vector<vector<bool>> conflict(n, vector<bool>(n, false));for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {conflict[i][j] = conflict[j][i] = isConflict(trees[i], trees[j]);}}// 分解连通分量auto components = findComponents(conflict);int totalSum = 0;for (const auto& comp : components) {if (comp.empty()) continue;// 提取当前分量的树vector<Tree> compTrees;for (int idx : comp) {compTrees.push_back(trees[idx]);}int compSize = compTrees.size();// 构建分量冲突矩阵vector<vector<bool>> compConflict(compSize, vector<bool>(compSize, false));for (int i = 0; i < compSize; ++i) {for (int j = i + 1; j < compSize; ++j) {compConflict[i][j] = compConflict[j][i] = isConflict(compTrees[i], compTrees[j]);}}int compBest = 0;// 小分量用状态压缩DPif (compSize <= 15) {compBest = dpComp(compTrees, compConflict);} // 大分量用DFS+剪枝else {// 计算后缀和（从i开始的最大可能和）vector<int> suffix(compSize, 0);suffix[compSize-1] = compTrees.back().r * compTrees.back().r;for (int i = compSize-2; i >= 0; --i) {suffix[i] = suffix[i+1] + compTrees[i].r * compTrees[i].r;}vector<bool> selected(compSize, false);dfsComp(compTrees, compConflict, selected, 0, 0, compBest, suffix);}totalSum += compBest;}cout << totalSum << endl;return 0;
}

代码解析

1. ​​冲突检测优化​​：

   • 使用distSq计算圆心距平方（整数运算避免浮点误差）
   • isConflict通过圆心距² < (r₁ + r₂)²判断冲突

2. ​​连通分量分解​​：

   • findComponents用BFS将树分组
   • 不同分量完全独立，减少搜索空间

3. ​​混合求解策略​​：

   • ​​≤15节点​​：状态压缩DP（dpComp），用位掩码表示选择状态
   • ​​>15节点​​：DFS（dfsComp）配合后缀和剪枝

4. ​​关键优化点​​：

   • 按半径降序排序（使剪枝更早生效）
   • 后缀和数组（快速计算剩余最大可能值）
   • 状态压缩DP（高效处理小分量）

5. ​​时间复杂度​​：

   • 最坏情况：O(2^(n/2))（优于朴素O(2^n)）
   • 平均情况：O(n² + k·2^(m))（m为最大分量大小）

实例验证

输入样例：

6
1 1 2
1 4 2
1 7 2
4 1 2
4 4 2
4 7 2

执行过程：

1. ​​连通分量分解​​：6棵树全连通（因(1,1)与(4,1)冲突）
2. ​​分量求解​​：
   • 分量大小6 ≤ 15 → 状态压缩DP
   • 有效组合：{(1,1,2), (1,7,2), (4,4,2)}
   • 半径平方和 = 2² + 2² + 2² = 12
3. ​​输出结果​​：12 ✓

其他测试：

测试场景	输入特征	输出	验证结果
单棵树	[(0,0,5)]	25	✓
全冲突	[(0,0,1),(0,0,2),(0,0,3)]	9	✓
无冲突	[(0,0,1),(3,0,1),(6,0,1)]	3	✓
链式冲突	[(0,0,2),(0,3,2),(0,6,2)]	8	✓

注意事项

1. ​​精度处理​​：

   • 全程使用整数运算（圆心距²和半径和²）
   • 避免浮点数比较误差

2. ​​边界条件​​：

   • 单棵树直接返回r²
   • 空输入返回0
   • 全冲突时选最大单树

3. ​​特殊场景​​：

   • 圆心重合时：任意两棵树都冲突
   • 超大半径树：可能"吞并"周围所有树
   • 分散小树群：独立分量加速处理

测试点设计

测试类型	测试数据	验证重点
功能测试	示例输入	基础功能
边界测试	n=1, n=30	极端输入
冲突测试	全冲突/无冲突	选择逻辑
精度测试	临界距离(r₁+r₂)²±1	冲突判断
性能测试	n=30随机数据	运行时间≤1s

优化建议

1. ​​迭代加深搜索​​：

   // 限制深度逐步增加
   for (int depth = 1; depth <= maxDepth; depth++) {if (dfsWithDepthLimit(...)) break;
   }

2. ​​启发式排序​​：

   // 按冲突度排序（高冲突树优先）
   sort(trees.begin(), trees.end(), [&](Tree a, Tree b) {return conflictCount[a.id] > conflictCount[b.id];
   });

3. ​​并行计算​​：

   #pragma omp parallel for
   for (auto& comp : components) {solveComponent(comp);
   }

4. ​​记忆化搜索​​：

   unordered_map<string, int> memo; // 状态缓存