[ICPC 46th Shanghai] Life is a Game 克鲁斯卡尔重构树

简介: 题目大意:给定n个点,m条边,有q个询问每个点有一个(能量值)点权,每条边有一个边权m条边描述为u v w表示有一条u与v相连的边权为w的通路在每一次询问中,给定一个点x和现有的能量值k,每次只能是在当前能量值大于边权的时候到达另一个点,并获取这个点的能量值(路可以重复走),问最终能够获得多大的能量值

题目链接


题目大意:


给定n个点,m条边,有q个询问

每个点有一个(能量值)点权,每条边有一个边权

m条边描述为u v w表示有一条u与v相连的边权为w的通路


在每一次询问中,给定一个点x和现有的能量值k,每次只能是在当前能量值大于边权的时候到达另一个点,并获取这个点的能量值(路可以重复走),问最终能够获得多大的能量值


思路:


克鲁斯卡尔重构树

在建立克鲁斯卡尔重构树的时候,会将边权化为点权来处理并建立成一个堆,而且原先的节点一定是重构树中的 叶子节点 ,除了叶子节点之外的其他点都是原先的边权

在克鲁斯卡尔重构树中,从叶子节点以上到根的路径中,点权一定是单调不减的


所以说给定的节点要是能够直接跳到祖先节点的话,那么说以这个节点为根的子树都能够访问到

所以说在这里可以使用倍增来处理,并且在维护以某节点为根的子树的所有节点的能量值

这样如果说能够跳过去的话,就将能量值的贡献加过去,直到不能跳为止


code:


ll fa[maxn],siz[maxn],a[maxn];
vector<int> gra[maxn];
ll bz[27][maxn],n,m,cnt,q;
struct node {
  int u,v,w;
  friend bool operator<(node a,node b) {
    return a.w < b.w;
  }
  node() {  }
  node(int _u,int _v,int _w) {
    u = _u,v = _v,w = _w;
  }
};
vector<node> vet;
int get(int x) {
  if(x == fa[x]) return x;
  else return fa[x] = get(fa[x]);
}
void init() {
  for(int i=0; i<=n*2; i++) fa[i] = i;//,siz[i] = 1;
}
void kru() {
  sort(vet.begin(),vet.end());
  for(int i=0; i<m; i++) {
    node nd = vet[i];
    int u = nd.u,v = nd.v,w = nd.w;
    int fau = get(u);
    int fav = get(v);
    if(fau != fav) {
      a[++cnt] = w;
      fa[cnt] = fa[fau] = fa[fav] = cnt;
      gra[fau].push_back(cnt);
      gra[cnt].push_back(fau);
      gra[fav].push_back(cnt);
      gra[cnt].push_back(fav);
    }
  }
}
void dfs(int u,int fa) {
  bz[0][u] = fa;
  for(int i=1; i<=20; i++) {
    bz[i][u] = bz[i-1][bz[i-1][u]];
  }
  for(int to:gra[u]) {
    if(to == fa) continue;
    dfs(to,u);
    siz[u] += siz[to];
  }
}
int main() {
  n = read,m = read,q = read;
  init();
  cnt = n;
  for(int i=1; i<=n; i++) siz[i] = read;
  for(int i=1; i<=m; i++) {
    int u = read,v = read,w = read;
    vet.push_back(node {u,v,w});
  }
  kru();
  dfs(cnt,0);
  a[0] = ((1LL<<31)-1);
  for(int i=1; i<=q; i++) {
    ll u = read,s = read;
    ll now = s + siz[u];
    while(u != cnt) {
      int tu = u;
      for(int i=20; i>=0; i--) {
        if(a[bz[i][u]] <= now) u = bz[i][u];
      }
      if(tu == u) break;
      now = siz[u] + s;
    }
//    printf("->>>> %lld\n",now);
        printf("%lld\n",now);
  }
  return 0;
}
/**
**/




目录
相关文章
|
8月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-529 DOTA
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-529 DOTA
40 0
|
8月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-91 Anagrams问题
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-91 Anagrams问题
50 0
|
8月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-986 藏匿的刺客
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-986 藏匿的刺客
106 0
|
8月前
|
存储 C++
【C++练级之路】【Lv.15】AVL树(双子旋转,领略绝对平衡之美)
【C++练级之路】【Lv.15】AVL树(双子旋转,领略绝对平衡之美)
【C++练级之路】【Lv.15】AVL树(双子旋转,领略绝对平衡之美)
|
机器学习/深度学习
UPC - 2022春混合个人训练赛第五场 D Seahorse Shoes(贪心+模拟)
UPC - 2022春混合个人训练赛第五场 D Seahorse Shoes(贪心+模拟)
94 0
|
8月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-380 绘制地图
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-380 绘制地图
46 0
2022天梯赛三月冲刺——PAT (Advanced Level)1013 Battle Over Cities (并查集找连通块)
2022天梯赛三月冲刺——PAT (Advanced Level)1013 Battle Over Cities (并查集找连通块)
120 0
|
机器学习/深度学习 安全
洛谷P2245 星际导航(kruskal重构树)
洛谷P2245 星际导航(kruskal重构树)
124 0
(数学)(必要解题步骤)2021icpc上海D. Strange Fractions
(数学)(必要解题步骤)2021icpc上海D. Strange Fractions
90 0
|
机器学习/深度学习 Windows
The 2022 ICPC Asia Regionals Online Contest (I)-D题题解(DFS暴搜+剪枝+打表去重+二分)
时间复杂度:O(227 + nlog(n) + T * log(n)),227是DFS打表的时间,nlog(n)是vertor排序的时间,T*log(n)是询问次数和二分搜答案的时间。(如果算错了,评论或者私信指出谢谢)
178 0
The 2022 ICPC Asia Regionals Online Contest (I)-D题题解(DFS暴搜+剪枝+打表去重+二分)