复赛二:赛道修建(track)

洛谷:P5021 
OJ: I5021

数据结构和变量:

  • 邻接表(adj)
    • 使用 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] 为未被选中的最长部分路径,以便父节点使用。

主函数

  1. 初始化邻接表
    • 使用 adj[i].clear(); 清空每个节点的边列表,确保邻接表开始时为空。
  2. 输入数据
    • 输入节点数 n 和需要形成的赛道数 m
    • 输入 n-1 条边的信息,并通过 Addline 函数构建邻接表。
  3. 选择根节点
    • 随机选择一个根节点(1 到 n 之间)。
  4. 二分查找
    • 目标是找到最大的 ans,使得可以形成至少 m 条长度 ≥ ans 的赛道。
    • 初始左右边界分别为 0INF
    • 在每次迭代中,计算中位数 mid 作为当前的最小赛道长度候选值。
    • 通过执行 DFS 函数,判断是否可以形成至少 m 条赛道。
    • 如果可以,更新答案 ansmid,并尝试寻找更大的最小赛道长度。
    • 否则,尝试寻找更小的最小赛道长度。
  5. 输出结果
    • 最终输出满足条件的最大可能的最小赛道长度 ans

时间复杂度分析

  • 二分查找的时间复杂度为O(log S),其中S是所有边长度的总和。
  • 每次DFS的时间复杂度为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;
}
Scroll to Top