2021icpc上海H

发表于2021-11-30更新于2022-04-08阅读次数

好题好题

Life is a game

题意：
n 个点 m 条边，有点权和边权，q 个询问，每个询问 x,k 表示从 x 出发，带着 k 的能力，通过一条边的条件是能力大于这条边的权值，当第一次到达一个点时可以将该点的权值累加到能力上，求可以获得的最大能力。

法一、并查集

考虑离线询问，每个点带有若干个询问，每个询问包含初试能力值和询问ID。然后从小到大枚举每条边(x,y,w)，设 v[x] 是 x 的点权，那么对于从 x 出发的询问，如果能力值 k+v[x]<w，那么说明它无法到达除去 x 之外的所有点，它的答案就是 k+v[x]，紧接着把该询问从 x 的询问集合中删除。之后对于 y 做同样的处理。

此时，x 和 y 中询问都可以通过 (x,y,w) 这条边，所以，可以将 x 与 y 合并成一个集合，然后该集合的点权和就是 v[x]+v[y]。这里可以用一个带权并查集合并。另外询问也需要合并，按照启发式合并的思想，每次小的集合向大的集合合并即可。

总体复杂度为 O(mlogm+qlog2q) 。

法二、kruskal重构树

⼀张带边权带点权⽆向图。从某点出发，有初始声望。每第⼀次到达⼀个点将获得点权等值的声望加成。
经过⼀条边需要满⾜边权等值的最低声望限制。多次给出起点和初始声望，询问能达到的最⼤声望。
按照边权从⼩到⼤建⽴ Kruskal 重构树。每次询问都是从叶⼦出发，在树上倍增。向上找到第⼀条不能通过的边（即，该边
下⾯的⼦树的 叶⼦点权和 加上 初始声望 ⼩于该边边权），把下⾯⼦树的 叶⼦点权和 加上 初始声望 即为答案。
复杂度O((n + m)log m + q log n)

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
/*
* @Author: Marhoosh
* @Date:   2021-07-22 10:27:29
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-11-30 19:43:14
*/
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=1e5+11;
struct Edge{
    ll u,v,w;
    bool operator < (const Edge& b) const {
        return w<b.w;
    }
}e[maxn];
ll val[maxn],fa[maxn],ans[maxn];
ll n,m,q;
priority_queue<P,vector<P>,greater<P>> st[maxn];
ll found(ll x){return fa[x]==x?x:fa[x]=found(fa[x]);}
void solve(){
    sort(e+1,e+1+m);
    for(ll i=1;i<=m;i++){
        ll u=e[i].u,v=e[i].v,w=e[i].w;
        u=found(u),v=found(v);
        if(u==v)  continue;
        while(!st[u].empty() && st[u].top().first+val[u]<w){
            ans[st[u].top().second]=st[u].top().first+val[u];
            st[u].pop();
        }
        while(!st[v].empty() && st[v].top().first+val[v]<w){
            ans[st[v].top().second]=st[v].top().first+val[v];
            st[v].pop();
        }
        if(st[u].size()>st[v].size())  swap(u,v);
        while(!st[u].empty()){
            st[v].push(st[u].top());
            st[u].pop();
        }
        fa[u]=v;
        val[v]+=val[u];
    }
    for(ll i=1;i<=n;i++){
        ll x=found(i);
        while(!st[x].empty()){
            ans[st[x].top().second]=st[x].top().first+val[x];
            st[x].pop();
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>q;
    for(ll i=1;i<=n;i++)  fa[i]=i;
    for(ll i=1;i<=n;i++)  cin>>val[i];
    for(ll i=1;i<=m;i++){
        ll u,v,w;cin>>u>>v>>w;
        e[i]={u,v,w};
    }
    for(ll i=1;i<=q;i++){
        ll u,k;cin>>u>>k;
        st[u].push({k,i});
    }
    solve();
    for(ll i=1;i<=q;i++)  cout<<ans[i]<<"\n";
    return 0;
}