「CodeForces-1253F」Cheap Robot(最小瓶颈路)

发表于 | 分类于 ，

F - Cheap Robot
给定一个无向图，其中1-k为充电桩。经过长度为w的边会消耗w的电量，可在任意充电桩充满电。q次询问，每次询问从一个充电桩到另一个充电桩所需要的最小电池容量。

题意

给定一个无向图，其中1-k为充电桩。经过长度为w的边会消耗w的电量，可在任意充电桩充满电。q次询问，每次询问从一个充电桩到另一个充电桩所需要的最小电池容量。

题解

对于任意一个非充电桩的点，其必须满足以下两个条件：

  1. 在这个点的电量必须能够到达最近的充电桩；
  2. 从这个点到最近的充电桩后返回这个点，它的总电量不能减少；

考虑将原图缩为k个联通块，构建一张新图。

对于原图建立超级源点，点1-k向0点连边，求出距离每个非关键点最近的充电桩，以及它到最近充电桩的距离$dis[i]$。

对图上的两个非关键点$(u,v)$，点$u$能到达点$v$当且仅当电量$c$满足$(c-dis[u])-w≥dis[v]$，即$c≥dis[u]+dis[v]+w$。

对原图上的每条边更新，如果两个点$(u,v)$不属于同一个联通块，在$(belong[u],belong[v])$加边，边权为$dis[u]+dis[v]+w$。

建完新图之后，问题转化为最小瓶颈路模板题。即给定一个k个节点m条边的图，回答q个询问，要求寻找从$s$到$t$的一条路径，使得路径上权值最大的一条边权值最小。

这个问题离线用MST上LCA搞一下就好。

代码

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
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
#define int long long
const int maxn = 3e5 + 10;
 
int head[maxn], dis[maxn], cnt, n, k;
struct Edge { int nex, to, w; } edge[2 * maxn];
struct E{ 
	int u, v, w;
	bool operator < (const E oth) const { return w < oth.w; }
} es[maxn];
int bel[maxn];
 
int pre[maxn];
int Find(int x) { return x == pre[x] ? x : pre[x] = Find(pre[x]); }
 
void add(int u, int v, int w)
{
	edge[++ cnt] = { head[u], v, w };
	head[u] = cnt;
}
 
void dij()
{
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que;
	memset(dis, 0x3f, sizeof dis);
	for(int i = 1; i <= k; i ++) bel[i] = i, dis[i] = 0, que.push({0, i});
	while(!que.empty())
	{
		auto f = que.top(); que.pop();
		int u = f.second, d = f.first;
		if(d != dis[u]) continue;
		for(int i = head[u]; i; i = edge[i].nex)
		{
			int v = edge[i].to, w = edge[i].w;
			if(dis[u] + w < dis[v]) 
			{
				bel[v] = bel[u];
				dis[v] = dis[u] + w;
				que.push({dis[v], v});
			}
		}
	}
}
 
int val[maxn << 1], idx;
vector<int> G[maxn << 1];
 
inline void merge(int u, int v)
{
	G[u].push_back(v);
	pre[v] = u;
}
 
int dep[maxn << 1], fa[maxn << 1][30];
 
void dfs(int u, int pre)
{
	dep[u] = dep[pre] + 1, fa[u][0] = pre;
	for(int i = 1; (1 << i) <= idx; i ++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for(auto v : G[u]) if(v != pre) dfs(v, u);
}
 
int LCA(int u, int v)
{
	if(dep[u] < dep[v]) swap(u, v);
	int d = dep[u] - dep[v];
	for(int i = 0; (1 << i) <= d; i ++) if((1 << i) & d) u = fa[u][i];
	if(u == v) return u;
	for(int i = 22; i >= 0; i --) if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}
 
signed main()
{
	int m, q, u, v, w;
	scanf("%lld%lld%lld%lld", &n, &m, &k, &q);
	for(int i = 1; i <= m; i ++)
	{
		scanf("%lld%lld%lld", &u, &v, &w);
		es[i] = { u, v, w };
		add(u, v, w);
		add(v, u, w);
	}
	dij();
	for(int i = 1; i <= m; i ++) if(bel[es[i].u] != bel[es[i].v]) es[i].w = es[i].w + dis[es[i].u] + dis[es[i].v];
	sort(es + 1, es + m + 1);
	for(int i = 1; i <= 2 * n; i ++) pre[i] = i;
	idx = k;
	for(int i = 1; i <= m; i ++)
	{
		int u = bel[es[i].u], v = bel[es[i].v], w = es[i].w;
		int fx = Find(u), fy = Find(v);
		if(fx == fy) continue;
		idx ++;
		merge(idx, fx);
		merge(idx, fy);
		val[idx] = w;
		if(idx == 2 * k - 1) break;
	}
	dfs(idx, 0);
	while(q --)
	{
		int u, v;
		scanf("%lld%lld", &u, &v);
		printf("%lld\n", val[LCA(u, v)] ? val[LCA(u, v)] : -1);
	}
	return 0;
}