洛谷:P5021
OJ: I5021
数据结构和变量:
vector<vector<pair<int, int>>> adj(MAXN);
来表示邻接表。adj[x]
存储所有与节点 x
相连的边,每条边由一个 pair
表示,包含目标节点和边的权重。dp[MAXN]
:存储每个节点向上延伸的最长路径长度。tag[MAXN]
:用于标记路径是否已被选中,避免重复使用。que[MAXN]
:用于存储当前节点的所有部分路径长度。tail
:指示 que
数组中有效部分路径的数量。res
:表示剩余需要形成的赛道数。DFS函数功能:
通过DFS遍历树,计算在给定最小赛道长度 lim
下,可以形成多少条满足条件的赛道。
对于每个节点 x
,递归处理其所有子节点,收集子节点向上延伸的部分路径长度。
将收集到的部分路径进行排序,然后尝试直接选择那些已经大于等于 lim
的路径作为独立赛道。
对剩余的较小路径进行配对,尝试形成更多满足条件的赛道。
更新 dp[x]
为未被选中的最长部分路径,以便父节点使用。
主函数:
adj[i].clear();
清空每个节点的边列表,确保邻接表开始时为空。n
和需要形成的赛道数 m
。n-1
条边的信息,并通过 Addline
函数构建邻接表。ans
,使得可以形成至少 m
条长度 ≥ ans
的赛道。0
和 INF
。mid
作为当前的最小赛道长度候选值。DFS
函数,判断是否可以形成至少 m
条赛道。ans
为 mid
,并尝试寻找更大的最小赛道长度。ans
。时间复杂度分析:
O(log S)
,其中S
是所有边长度的总和。O(n log n)
,因为在DFS中对部分路径进行排序。O(n log n * log S)
,适用于较大的输入规模(如n
达到5e4
)。代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 | #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; // 常量定义 const int MAXN = 50005; // 最大节点数 const int INF = 0x7fffffff; // 无穷大,用于初始化右边界 // 使用邻接表存储树的边,vector中存储<pair<目标节点, 边权重>> vector<vector<pair<int, int>>> adj(MAXN); // 节点数和需要形成的赛道数 int n, m; // DFS使用的数组 int dp[MAXN]; // dp[x]表示从节点x向上延伸的最长路径长度 int tag[MAXN]; // tag数组用于标记路径是否已被选中 int que[MAXN]; // que数组用于存储当前节点的所有部分路径长度 int tail; // que数组的尾指针 int res; // 剩余需要形成的赛道数 //向邻接表中添加一条边, x 起始节点编号, y目标节点编号, z 边的权重(长度)。 inline void Addline(int x, int y, int z){ adj[x].push_back(make_pair(y, z)); // 使用 push_back 添加从x到y的边 adj[y].push_back(make_pair(x, z)); // 使用 push_back 添加从y到x的边(因为树是无向的) // adj[x].emplace_back(y, z); // adj[y].emplace_back(x, z); } /*深度优先搜索,用于计算在给定最小长度lim下,可以形成的赛道数量。 x 当前处理的节点编号, from 当前节点的父节点编号,以避免回溯。lim 当前候选的最小赛道长度。*/ void DFS(int x, int from, int lim){ // 遍历所有与x相连的节点(子节点) for (const auto &edge : adj[x]){ int child = edge.first; int weight = edge.second; if (child == from) continue; // 避免回到父节点 // 递归调用DFS处理子节点 DFS(child, x, lim); } // 初始化部分路径队列的尾指针 tail = 0; // 收集所有子节点向上延伸的部分路径长度 for (const auto &edge : adj[x]) { int child = edge.first; int weight = edge.second; if (child == from) continue; que[++tail] = dp[child] + weight; // 将子节点的最长路径加上边的长度 } // 将部分路径按升序排序 sort(que + 1, que + tail + 1); // 尝试直接选择那些已经大于等于lim的部分路径作为独立的赛道 while (tail > 0 && que[tail] >= lim){ tail--; // 移除最大的部分路径 res--; // 需要形成的赛道数减少 } // 尝试将剩余的较小路径与较大路径配对,形成赛道 for (int i = 1; i <= tail; i++){ if (tag[i] != x){ // 检查该路径是否未被选中 int l = i + 1; int r = tail; int pst = tail + 1; // 初始化二分查找的目标位置 // 二分查找,寻找最小的j使得que[i] + que[j] >= lim while (l <= r){ int mid = (l + r) / 2; if (que[i] + que[mid] >= lim){ pst = mid; r = mid - 1; } else{ l = mid + 1; } } // 如果找到的pst已经被选中,继续向后寻找 while (pst <= tail && tag[pst] == x) pst++; // 如果找到合适的配对,标记这两条路径并减少剩余赛道数 if (pst <= tail) { tag[i] = tag[pst] = x; // 标记这两条路径已被选中 res--; // 需要形成的赛道数减少 } } } // 更新当前节点x的dp值,选择未被选中的最长部分路径向上传递 dp[x] = 0; for (int i = tail; i >= 1; i--){ if (tag[i] != x){ dp[x] = que[i]; break; // 找到第一个未被选中的最长路径 } } return; } int main(){ //freopen("track.in","r",stdin); //freopen("track.out","w",stdout); // 输入节点数n和需要形成的赛道数m cin >> n >> m; // 输入n-1条边的信息,并构建邻接表 for (int i = 1, x, y, z; i < n; i++){ cin>>x>>y>>z; Addline(x, y, z); // 添加从x到y的边和从y到x的边 } int root = 1; // 初始化二分查找的左右边界 int l = 0, r = INF, ans = 0; while (l <= r){ // 二分查找答案 int mid = (l + r) / 2; // 当前候选的最小赛道长度 res = m; // 重置剩余需要的赛道数 memset(tag, 0, sizeof(tag)); // 重置标记数组 DFS(root, 0, mid); // 执行DFS,计算可以形成的赛道数量 if (res <= 0){ // 如果可以形成足够的赛道,尝试更大的最小长度 ans = mid; l = mid + 1; } else{ // 如果无法形成足够的赛道,尝试更小的最小长度 r = mid - 1; } } // 输出最终的答案 cout << ans << endl; return 0; } |