Life is a Game
#最小生成树 #重构树 #图论 #贪心
题目描述
A good problem should have a concise statement.
You are given an array
a
a
a of length
n
n
n, initially filled with zeros, and another array
b
b
b of length
n
n
n. Your goal
is to transform array
a
a
a into array
b
b
b. You can perform the following two types of operations:
•
1
x
:
1 \ x:
1 x: Add
1
1
1 to all elements in a that are equal to
x
.
x.
x.
•
2
x
:
2 \ x:
2 x: Add
1
1
1 to the element in a at index
x
.
x.
x.
You can perform no more than
20000
20 000
20000 operations.
输入格式
The first line contains three integers n , m , q ( 1 ≤ n , m , q ≤ 1 0 5 ) n,m,q\,(1\le n,m,q \le 10^5) n,m,q(1≤n,m,q≤105), denoting the number of cities, roads and game saves respectively.
The second line contains n n n integers a 1 , a 2 , ⋯ , a n ( 1 ≤ a i ≤ 1 0 4 ) a_1, a_2, \cdots, a_n\,(1\le a_i \le 10^4) a1,a2,⋯,an(1≤ai≤104), denoting the bonus social ability points for the cities.
Following m m m lines each contains three integers u , v , w , ( 1 ≤ u ≤ v ≤ n , 1 ≤ w ≤ 1 0 9 ) u, v, w\ ,(1 \leq u \leq v \leq n, 1\leq w \leq 10^9) u,v,w ,(1≤u≤v≤n,1≤w≤109), denoting that cities u , v u,v u,v are undirectedly connected by a road of ability threshold w w w.
Following q q q lines each contains two integers x , k ( 1 ≤ x ≤ n , 1 ≤ k ≤ 1 0 9 ) x, k\,(1\le x \le n, 1\le k \le 10^9) x,k(1≤x≤n,1≤k≤109), denoting the game saves.
输出格式
Input
The first line contains three integers n , m , q ( 1 ≤ n , m , q ≤ 1 0 5 ) n,m,q\,(1\le n,m,q \le 10^5) n,m,q(1≤n,m,q≤105), denoting the number of cities, roads and game saves respectively.
The second line contains n n n integers a 1 , a 2 , ⋯ , a n ( 1 ≤ a i ≤ 1 0 4 ) a_1, a_2, \cdots, a_n\,(1\le a_i \le 10^4) a1,a2,⋯,an(1≤ai≤104), denoting the bonus social ability points for the cities.
Following m m m lines each contains three integers u , v , w , ( ≤ u ≤ v ≤ n , 1 ≤ w ≤ 1 0 9 ) u, v, w\ ,(\leq u \leq v \leq n, 1\leq w \leq 10^9) u,v,w ,(≤u≤v≤n,1≤w≤109), denoting that cities u , v u,v u,v are undirectedly connected by a road of ability threshold w w w.
Following q q q lines each contains two integers x , k ( 1 ≤ x ≤ n , 1 ≤ k ≤ 1 0 9 ) x, k\,(1\le x \le n, 1\le k \le 10^9) x,k(1≤x≤n,1≤k≤109), denoting the game saves.
样例 #1
样例输入 #1
8 10 2
3 1 4 1 5 9 2 6
1 2 7
1 3 11
2 3 13
3 4 1
3 6 31415926
4 5 27182818
5 6 1
5 7 23333
5 8 55555
7 8 37
1 7
8 30
样例输出 #1
16
36
解法
首先，从一个点出发到达另一个点，如果两点之间有多条路径，那么我们一定走最长边最短的那一条路径，这样我们才有更高的可能到达这个点。
因此，容易发现，使得图联通的情况下，最优的情况就是最小生成树了。
现在的问题转换为，如何从最小生成树的任意一个点判断最多能获得多少贡献。
因为我们的边是双向边，并且我们能够走回头路，因此我们最优的情况一定是先把边权小的边走了，获得了相应点的点权之后，回过头来继续走边权大的点。
确定了策略，如何优化查询呢？
回顾 k r u s k a l kruskal kruskal重构树，我们知道原图中任意两点之间的最长边可以被转换为重构树上非叶子节点的点权，如下图：
那么我们可以利用倍增的思想，预处理出叶子节点向这条链跳的最大的边权和获得点权之间的关系，即边权-点权最大值，往根节点的这一段是递增的。
每次我们初始获得的价值，都可以倍增的向上跳，价值不够继续跳了，那么答案就是这个点以下的所有的叶子节点的权重，因为在重构树上叶子节点的权重为原图中的点权。
这样整体复杂度在 O ( m l o g 2 m + q l o g 2 n ) O(mlog_2m + qlog_2n) O(mlog2m+qlog2n)
代码
const int N = 2e5 + 10;
int n, m, q,tot;
int a[N],w[N],p[N];
struct node {
int u, v, dis;
bool operator<(const node& x)const {
return dis < x.dis;
}
}edge[N];
int find(int x) {
return p[x] = p[x] == x ? x : find(p[x]);
}
vector<int>e[N];
void kruskal() {
sort(edge + 1, edge + 1 + m);
for (int i = 1; i <= 2 * n + 1; ++i) {
p[i] = i;
}
for (int i = 1; i <= m; ++i) {
int u = edge[i].u, v = edge[i].v, dis = edge[i].dis;
int pu = find(u), pv = find(v);
if (pu != pv) {
p[pv] = p[pu] = ++tot;
e[tot].push_back(pu);
e[tot].push_back(pv);
w[tot] = dis;
}
}
}
int fa[N][21];
int d[N];
void dfs(int u) {
for (auto& v : e[u]) {
fa[v][0] = u;
for (int i = 1; i <= 20; ++i) {
fa[v][i] = fa[fa[v][i - 1]][i - 1];
}
dfs(v);
a[u] += a[v];
}
d[u] = w[fa[u][0]] - a[u];
}
int c[N][21];
void dfs2(int u) {
for (auto& v : e[u]) {
c[v][0] = d[v];
for (int i = 1; i <= 20; ++i) {
c[v][i] = std::max(c[v][i - 1], c[fa[v][i - 1]][i - 1]);
}
dfs2(v);
}
}
void solve() {
cin >> n >> m >> q;
tot = n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= m; ++i) {
int u, v, dis;
cin >> u >> v >> dis;
edge[i] = { u,v,dis };
}
kruskal();
dfs(tot);
dfs2(tot);
a[0] = a[tot];
while (q--) {
int x, k;
cin >> x >> k;
for (int i = 20; i >= 0; --i) {
if (c[x][i] <= k) {
x = fa[x][i];
}
}
std::cout << a[x] + k << "\n";
}
}
signed main() {
ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
};