CF1253F Cheap robot

发表于 | 阅读数

给你一张图，每条边消耗的电量，$1..k$为充电桩，可以充到$c$.

$q$次询问，每次询问两个充电桩之间最少需要多少$c$。

想到在两两充电桩之间构建新的边，如何建呢？使两两之间新边距离最短。（不可能对每一个充电桩跑一边$dijkstar$)
可以先对所有充电桩建立一个最大源点。$dis[u]$为离最近充电桩的距离

对于每一条原边$(u,v,w)$，$c>=dis_u+dis_v+w。$那么问题变成求一条从 𝑎 到 𝑏 的路径使得路径上每条边的$𝑑𝑖𝑠_𝑢+𝑑𝑖𝑠_𝑣+𝑤$的最大值最小（明显是满足条件的最小的 𝑐）。

然后我们把每条边建好，发现若$1->2->3$和$1->3$不需要重复，只需要选择最小的，因为题目是为了最大值最小。这样就是最小生成树的思想。 （建树即可）。

题意就成了求树上两点之间边的最大值。$lca \ is \ ok$


代码

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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
const int M = 3e5 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
struct edge
{
    int to, u, nxt;
    ll w;
    friend bool operator<(edge a, edge b)
    {
        return a.w < b.w;
    }
} e[M << 1], a[M], ee[M], te[N << 1];
int head[N], thead[N], cnt, tcnt;
struct heapnode
{
    int x;
    ll dis;
    heapnode(int _x, ll _dis) : x(_x), dis(_dis) {}
    friend bool operator<(heapnode a, heapnode b)
    {
        return a.dis > b.dis; //结构体中，x小的优先级高
    }
};
//vector<edge> g[N], tr[N];
void addadge(int u, int v, ll w)
{
    e[++cnt].to = v;
    e[cnt].w = w;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}
int n, k, m, q;
ll dis[N];
int fc[N], vis[N];
void  ()
{
    priority_queue<heapnode> q;
    for (int i = 1; i <= n; i++)
        dis[i] = inf, vis[i] = 0;
    for (int i = 1; i <= k; i++)
    {
        dis[i] = 0;
        fc[i] = i;
        q.push(heapnode(i, 0));
    }
    while (!q.empty())
    {
        int x = q.top().x;
        q.pop();
        if (vis[x])
            continue;
        vis[x] = 1;
        for (int i = head[x]; i; i = e[i].nxt)
        {
            int to = e[i].to;
            ll w = e[i].w;
            if (dis[to] > dis[x] + w)
            {
                dis[to] = dis[x] + w;
                fc[to] = fc[x];
                q.push(heapnode(to, dis[to]));
            }
        }
    }
}
int father[N], deep[N];
int fa[N][21], tt;
ll fm[N][21];
int find(int x)
{
    if (father[x] != x)
        return father[x] = find(father[x]);
    return x;
}
void addtree(int u, int v, ll w)
{
    te[++tcnt].to = v;
    te[tcnt].w = w;
    te[tcnt].nxt = thead[u];
    thead[u] = tcnt;
}
void dfs(int x, int f)
{
    for (int i = 1; i <= tt; i++)
    {
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
        fm[x][i] = max(fm[x][i - 1], fm[fa[x][i - 1]][i - 1]);
    }
    for (int i = thead[x]; i; i = te[i].nxt)
    {
        int to = te[i].to;
        if (to == f)
            continue;
        fa[to][0] = x;
        fm[to][0] = te[i].w;
        deep[to] = deep[x] + 1;
        dfs(to, x);
    }
}
void build()
{
    for (int i = 1; i <= m; i++)
    {
        int u = fc[a[i].u];
        int to = fc[a[i].to];
        ll w = dis[a[i].u] + dis[a[i].to] + a[i].w;
        ee[i].u = u, ee[i].to = to, ee[i].w = w;
    }
    int trnum = 0;
    sort(ee + 1, ee + 1 + m);
    for (int i = 1; i <= k; i++)
        father[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int x = find(ee[i].u);
        int y = find(ee[i].to);
        if (x != y)
        {
            ++trnum;
            father[x] = y;
            addtree(ee[i].u, ee[i].to, ee[i].w);
            addtree(ee[i].to, ee[i].u, ee[i].w);
        }
        if (trnum == k - 1)
            break;
    }
    dfs(1, -1);
}
ll lca(int u, int v)
{
    ll res = 0;
    if (u == v)
        return res;
    if (deep[u] < deep[v])
        swap(u, v);
    //cout << u << " " << v << endl;
    for (int i = tt; i >= 0; i--)
        if (deep[fa[u][i]] >= deep[v])
        {
            res = max(res, fm[u][i]);
            u = fa[u][i];
        }

    if (u == v)
        return res;
    for (int i = tt; i >= 0; i--)
        if (fa[u][i] != fa[v][i])
        {
            res = max(res, max(fm[v][i], fm[u][i]));
            u = fa[u][i];
            v = fa[v][i];
        }
    res = max(res, max(fm[v][0], fm[u][0]));
    return res;
}
int main()
{

    scanf("%d%d%d%d", &n, &m, &k, &q);
    tt = (ll)(log(k) / log(2)) + 1;
    for (int i = 1; i <= m; i++)
    {

        scanf("%d%d%lld", &a[i].u, &a[i].to, &a[i].w);
        addadge(a[i].u, a[i].to, a[i].w);
        addadge(a[i].to, a[i].u, a[i].w);
    }
    dijkstra();
    build();
    for (int i = 1; i <= q; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        printf("%lld\n", lca(u, v));
    }
}

</details>