题意
⼀张带边权带点权⽆向图。从某点出发,有初始声望。每第⼀次到达⼀个点将获得点权等值的声望加成。经过⼀条边需要满⾜边权等值的最低声望限制。多次给出起点和初始声望,询问能达到的最⼤声望。
思路
对于图上路径边权值的限制,可以往kruskal重构树方向思考。构建出kruskal重构树就可以把边权转为点权,若求两点之间路径的限制,只需求lca的点权,这里可以和lca一样倍增向上跳。由于kruskal重构树中深度越深的点点权(原边权)越小,所以若能到达v,则以v为根的子树都可以到达。预处理出子树点权和后利用树上倍增就可以做到单词询问log的复杂度。
代码
// Problem: H. Life is a Game
// Contest: Codeforces - The 2021 ICPC Asia Shanghai Regional Programming Contest
// URL: https://codeforces.com/gym/103446/problem/H
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Time: 2022-11-03 21:27:46
//
// Powered by CP Editor (https://cpeditor.org)
//fw
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<cmath>
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define debug(a) cout<<#a<<"="<<a<<endl;
#define sv(a,l,r,x) for(int i=l;i<=r;i++)a[i]=x;
#define pii pair <int, int>
#define endl '\n'
#define pb push_back
#define lc u<<1
#define rc u<<1|1
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=2e5+10,M=2*N;
int h[N],e[M],ne[M],idx;
void add(int a,int b)
{
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
struct node
{
int u,v,w;
}edge[N];
int n,m,q,p[N],fa[N][20],cnt;
ll maxp[N];
ll a[N];
int find(int x)
{
return p[x]==x?x:p[x]=find(p[x]);
}
bool cmp(node a,node b)
{
return a.w<b.w;
}
int kruskal()
{
sort(edge+1,edge+1+m,cmp);
cnt=n;
for(int i=1;i<=n;i++)p[i]=i;
for(int i=1;i<=m;i++)
{
int u=edge[i].u,v=edge[i].v,w=edge[i].w;
u=find(u);v=find(v);
if(u!=v)
{
//建立重构树
maxp[++cnt]=w;
p[cnt]=p[u]=p[v]=cnt;
add(u,cnt);add(cnt,u);
add(v,cnt);add(cnt,v);
}
}
return cnt;
}
void dfs(int u,int ffa)
{
fa[u][0]=ffa;
for(int i=1;i<=19;i++)fa[u][i]=fa[fa[u][i-1]][i-1];//倍增能跳到的点
for(int i=h[u];~i;i=ne[i])
{
int ver=e[i];
if(ver==ffa)continue;
dfs(ver,u);
a[u]+=a[ver];
}
}
int main()
{
IOS
cin>>n>>m>>q;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
edge[i]={a,b,c};
}
n=kruskal();
// cout<<n<<endl;
dfs(n,0);
maxp[0]=1e18;//防止跳过头...
while(q--)
{
int x,k;
cin>>x>>k;
ll ans=a[x]+k;
while(x!=n)//有些点可能需要更新ans后再跳
{
int temp=x;
for(int i=19;i>=0;i--)
if(maxp[fa[x][i]]<=ans)
x=fa[x][i];
if(temp==x)break;//如果跳不动了
ans=a[x]+k;
}
cout<<ans<<endl;
}
return 0;
}
原文地址:http://www.cnblogs.com/avarice/p/16856092.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性