Luogu2993 FJOI2014 最短路径树问题 最短路树、长链剖分

时间:2022-09-24 19:22:53

传送门


强行二合一最为致命

第一问直接最短路+$DFS$解决

考虑第二问,与深度相关,可以考虑长链剖分。

设$f_{i,j}$表示长度为$i$,经过边数为$j$时的最大边权和,考虑到每一次从重儿子转移过来的时候,不仅要将$f$数组右移一格,还需要同时加上一个值。显然用线段树等数据结构额外维护是不现实的,我们考虑维护一个影响范围为整个$f_i$的加法标记$tag_i$,将$f_{i,0}$设置为$-tag_i$,每一次上传的时候把标记也一起上传,合并轻儿子、计算答案的时候将这个$tag$加上,就能够做到快速地维护了。

长链剖分代码比点分治还长……

 #include<bits/stdc++.h>
 #define P pair < int , int >
 #define int long long
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     ;
     char c = getchar();
     while(c != EOF && !isdigit(c)){
         if(c == '-')
             f = ;
         c = getchar();
     }
     while(c != EOF && isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return f ? -a : a;
 }

 ;
 vector < P > e[MAXN];
 struct edge{
     int end , upEd , w;
 }Ed[MAXN << ];
 ] , g[MAXN << ] , sz[MAXN] , tag[MAXN] , *dp[MAXN] , *cnt[MAXN];
 int *p1 = f , *p2 = g , N , M , K , cntEd , ans , times;
 priority_queue < P > q;
 bool vis[MAXN];

 inline void addEd(int a , int b , int c){
     Ed[++cntEd].end = b;
     Ed[cntEd].upEd = head[a];
     Ed[cntEd].w = c;
     head[a] = cntEd;
 }

 void Dijk(){
     q.push(P( , ));
     memset(dis , 0x3f , sizeof(dis));
     dis[] = ;
     while(!q.empty()){
         P t = q.top();
         q.pop();
         if(-t.first > dis[t.second])
             continue;
          ; i < sz[t.second] ; ++i)
             if(dis[e[t.second][i].first] > dis[t.second] + e[t.second][i].second){
                 dis[e[t.second][i].first] = dis[t.second] + e[t.second][i].second;
                 q.push(P(-dis[e[t.second][i].first] , e[t.second][i].first));
             }
     }
 }

 void create(int now){
     vis[now] = ;
      ; i < sz[now] ; ++i)
         if(!vis[e[now][i].first] && dis[e[now][i].first] == dis[now] + e[now][i].second){
             addEd(now , e[now][i].first , e[now][i].second);
             addEd(e[now][i].first , now , e[now][i].second);
             create(e[now][i].first);
         }
 }

 void dfs1(int now , int pre){
     md[now] = dep[now] = dep[pre] + ;
     for(int i = head[now] ; i ; i = Ed[i].upEd)
         if(!dep[Ed[i].end]){
             dfs1(Ed[i].end , now);
             if(md[Ed[i].end] > md[now]){
                 md[now] = md[Ed[i].end];
                 son[now] = Ed[i].end;
                 len[now] = Ed[i].w;
             }
         }
 }

 void dfs2(int now){
     if(son[now]){
         dp[son[now]] = dp[now] + ;
         cnt[son[now]] = cnt[now] + ;
         dfs2(son[now]);
         tag[now] = tag[son[now]] + len[now];
         dp[now][] = -tag[now];
     }
     cnt[now][] = ;
     if(ans < dp[now][K] + tag[now]){
         ans = dp[now][K] + tag[now];
         times = cnt[now][K];
     }
     else
         if(ans == dp[now][K] + tag[now])
             times += cnt[now][K];
     for(int i = head[now] ; i ; i = Ed[i].upEd)
          && Ed[i].end != son[now]){
             dp[Ed[i].end] = p1;
             cnt[Ed[i].end] = p2;
             p1 += (md[Ed[i].end] - dep[Ed[i].end] + ) << ;
             p2 += (md[Ed[i].end] - dep[Ed[i].end] + ) << ;
             dfs2(Ed[i].end);
              ; j <= md[Ed[i].end] - dep[Ed[i].end] && j <= K -  ; ++j)
                  - j)
                      - j] + Ed[i].w){
                         ans = tag[Ed[i].end] + dp[Ed[i].end][j] + tag[now] + dp[now][K -  - j] + Ed[i].w;
                         times = cnt[Ed[i].end][j] * cnt[now][K -  - j];
                     }
                     else
                          - j] + Ed[i].w)
                             times += cnt[Ed[i].end][j] * cnt[now][K -  - j];
              ; j <= md[Ed[i].end] - dep[Ed[i].end] +  && j <= K ; ++j)
                 ] + tag[Ed[i].end] + Ed[i].w - tag[now]){
                     dp[now][j] = dp[Ed[i].end][j - ] + tag[Ed[i].end] + Ed[i].w - tag[now];
                     cnt[now][j] = cnt[Ed[i].end][j - ];
                 }
                 else
                     ] + tag[Ed[i].end] + Ed[i].w - tag[now])
                         cnt[now][j] += cnt[Ed[i].end][j - ];
         }
 }

 signed main(){
 #ifndef ONLINE_JUDGE
     freopen("2993.in" , "r" , stdin);
     //freopen("2993.out" , "w" , stdout);
 #endif
     N = read();
     M = read();
     K = read() - ;
      ; i <= M ; ++i){
         int a = read() , b = read() , c = read();
         e[a].push_back(P(b , c));
         e[b].push_back(P(a , c));
         ++sz[a];
         ++sz[b];
     }
      ; i <= N ; ++i)
         sort(e[i].begin() , e[i].end());
     Dijk();
     create();
     dfs1( , );
     dp[] = p1;
     p1 += md[] << ;
     cnt[] = p2;
     p2 += md[] << ;
     dfs2();
     cout << ans << ' ' << times;
     ;
 }

Luogu2993 FJOI2014 最短路径树问题 最短路树、长链剖分的更多相关文章

  1. &lbrack;FJOI2014&rsqb;最短路径树问题 长链剖分

    [FJOI2014]最短路径树问题 LG传送门 B站传送门 长链剖分练手好题. 如果你还不会长链剖分的基本操作,可以看看我的总结. 这题本来出的很没水平,就是dijkstra(反正我是不用SPFA)的 ...

  2. Bzoj4016&sol;洛谷P2993 &lbrack;FJOI2014&rsqb; 最短路径树问题(最短路径问题&plus;长链剖分&sol;点分治)

    题面 Bzoj 洛谷 题解 首先把最短路径树建出来(用\(Dijkstra\),没试过\(SPFA\)\(\leftarrow\)它死了),然后问题就变成了一个关于深度的问题,可以用长链剖分做,所以我 ...

  3. bzoj 4016 &lbrack;FJOI2014&rsqb;最短路径树问题(最短路径树&plus;树分治)

    4016: [FJOI2014]最短路径树问题 Time Limit: 5 Sec  Memory Limit: 512 MBSubmit: 426  Solved: 147[Submit][Stat ...

  4. BZOJ&lowbar;4016&lowbar;&lbrack;FJOI2014&rsqb;最短路径树问题&lowbar;最短路&plus;点分治

    BZOJ_4016_[FJOI2014]最短路径树问题_最短路+点分治 Description 给一个包含n个点,m条边的无向连通图.从顶点1出发,往其余所有点分别走一次并返回. 往某一个点走时,选择 ...

  5. 洛谷 &lbrack;FJOI2014&rsqb;最短路径树问题 解题报告

    [FJOI2014]最短路径树问题 题目描述 给一个包含\(n\)个点,\(m\)条边的无向连通图.从顶点\(1\)出发,往其余所有点分别走一次并返回. 往某一个点走时,选择总长度最短的路径走.若有多 ...

  6. &lbrack;BZOJ4016&rsqb;&lbrack;FJOI2014&rsqb;最短路径树问题

    [BZOJ4016][FJOI2014]最短路径树问题 试题描述 给一个包含n个点,m条边的无向连通图.从顶点1出发,往其余所有点分别走一次并返回. 往某一个点走时,选择总长度最短的路径走.若有多条长 ...

  7. &lbrack;BZOJ4016&rsqb;&lbrack;FJOI2014&rsqb;最短路径树问题&lpar;dijkstra&plus;点分治&rpar;

    4016: [FJOI2014]最短路径树问题 Time Limit: 5 Sec  Memory Limit: 512 MBSubmit: 1796  Solved: 625[Submit][Sta ...

  8. 【BZOJ4016】&lbrack;FJOI2014&rsqb;最短路径树问题 最短路径树&plus;点分治

    [BZOJ4016][FJOI2014]最短路径树问题 Description 给一个包含n个点,m条边的无向连通图.从顶点1出发,往其余所有点分别走一次并返回. 往某一个点走时,选择总长度最短的路径 ...

  9. 【BZOJ4016】&lbrack;FJOI2014&rsqb;最短路径树问题(点分治,最短路)

    [BZOJ4016][FJOI2014]最短路径树问题(点分治,最短路) 题面 BZOJ 洛谷 题解 首先把最短路径树给构建出来,然后直接点分治就行了. 这个东西似乎也可以长链剖分,然而没有必要. # ...

随机推荐

  1. css实现文本框和下拉框结合的案例

    html 代码部分 <div id="list-name-input" class="list-name-input"> <select ty ...

  2. Swift扩展(Extension)

    在现有类和结构体的类型基础上,扩展新的功能. 语法: extension SomeType{ // new functionality to add to SomeType goes here } A ...

  3. SQL RIGHT JOIN 关键字

    SQL RIGHT JOIN 关键字 RIGHT JOIN 关键字会右表 (table_name2) 那里返回所有的行,即使在左表 (table_name1) 中没有匹配的行. RIGHT JOIN ...

  4. Sublime&lowbar;调试PHP编译系统设置&period;

    工具->编译系统->新建编译系统 {         "cmd": ["C:\\wampserver\\bin\\php\\php5.3.13\\php.ex ...

  5. word排版的一些小技巧积累

    先准备好样式 编辑前,可以先根据要求,设置好样式,可以免去编辑好后,再修改格式(这样要改好多文本的格式) docx doc的样式不能通用. .docx转.doc 从word2013自带的编辑公式,编辑 ...

  6. SSH密钥认证添加方法和一些实用配置

    更改SSH端口号 用账号密码进入主机 sudo nano /etc/ssh/sshd-config 再其中添加Port 22等或改变该条 添加公钥到主机 cd ~ sudo mkdir .ssh 此处 ...

  7. 30个值得关注的Vue开源项目

    译者按: 学习优秀的开源项目是提高代码水平最有效的方式. 原文: 30 Amazing Vue.js Open Source Projects for the Past Year (v.2018) 译 ...

  8. vue-cli使用swiper插件

    使用的教程https://blog.csdn.net/lbpro0412/article/details/82465067

  9. &commat;RequestParam接收解析不到 POST 提交的 数据

    1.使用postman或者其他发送请求模拟器进行模拟访问,需要指定Headers为Content-Type:application/x-www-form-urlencoded;指定body类型为x-w ...

  10. flow-vue&period;js移动端效果

    得益于vue.js和element,以及vue-element-extends在线表格编辑.前后端分离的后端用golang+beego框架,服务器采用腾讯云. vue的自适应做的很好,只要将侧栏加一行 ...