强行二合一最为致命
第一问直接最短路+$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 最短路径树问题 最短路树、长链剖分的更多相关文章
-
[FJOI2014]最短路径树问题 长链剖分
[FJOI2014]最短路径树问题 LG传送门 B站传送门 长链剖分练手好题. 如果你还不会长链剖分的基本操作,可以看看我的总结. 这题本来出的很没水平,就是dijkstra(反正我是不用SPFA)的 ...
-
Bzoj4016/洛谷P2993 [FJOI2014] 最短路径树问题(最短路径问题+长链剖分/点分治)
题面 Bzoj 洛谷 题解 首先把最短路径树建出来(用\(Dijkstra\),没试过\(SPFA\)\(\leftarrow\)它死了),然后问题就变成了一个关于深度的问题,可以用长链剖分做,所以我 ...
-
bzoj 4016 [FJOI2014]最短路径树问题(最短路径树+树分治)
4016: [FJOI2014]最短路径树问题 Time Limit: 5 Sec Memory Limit: 512 MBSubmit: 426 Solved: 147[Submit][Stat ...
-
BZOJ_4016_[FJOI2014]最短路径树问题_最短路+点分治
BZOJ_4016_[FJOI2014]最短路径树问题_最短路+点分治 Description 给一个包含n个点,m条边的无向连通图.从顶点1出发,往其余所有点分别走一次并返回. 往某一个点走时,选择 ...
-
洛谷 [FJOI2014]最短路径树问题 解题报告
[FJOI2014]最短路径树问题 题目描述 给一个包含\(n\)个点,\(m\)条边的无向连通图.从顶点\(1\)出发,往其余所有点分别走一次并返回. 往某一个点走时,选择总长度最短的路径走.若有多 ...
-
[BZOJ4016][FJOI2014]最短路径树问题
[BZOJ4016][FJOI2014]最短路径树问题 试题描述 给一个包含n个点,m条边的无向连通图.从顶点1出发,往其余所有点分别走一次并返回. 往某一个点走时,选择总长度最短的路径走.若有多条长 ...
-
[BZOJ4016][FJOI2014]最短路径树问题(dijkstra+点分治)
4016: [FJOI2014]最短路径树问题 Time Limit: 5 Sec Memory Limit: 512 MBSubmit: 1796 Solved: 625[Submit][Sta ...
-
【BZOJ4016】[FJOI2014]最短路径树问题 最短路径树+点分治
[BZOJ4016][FJOI2014]最短路径树问题 Description 给一个包含n个点,m条边的无向连通图.从顶点1出发,往其余所有点分别走一次并返回. 往某一个点走时,选择总长度最短的路径 ...
-
【BZOJ4016】[FJOI2014]最短路径树问题(点分治,最短路)
[BZOJ4016][FJOI2014]最短路径树问题(点分治,最短路) 题面 BZOJ 洛谷 题解 首先把最短路径树给构建出来,然后直接点分治就行了. 这个东西似乎也可以长链剖分,然而没有必要. # ...
随机推荐
-
css实现文本框和下拉框结合的案例
html 代码部分 <div id="list-name-input" class="list-name-input"> <select ty ...
-
Swift扩展(Extension)
在现有类和结构体的类型基础上,扩展新的功能. 语法: extension SomeType{ // new functionality to add to SomeType goes here } A ...
-
SQL RIGHT JOIN 关键字
SQL RIGHT JOIN 关键字 RIGHT JOIN 关键字会右表 (table_name2) 那里返回所有的行,即使在左表 (table_name1) 中没有匹配的行. RIGHT JOIN ...
-
Sublime_调试PHP编译系统设置.
工具->编译系统->新建编译系统 { "cmd": ["C:\\wampserver\\bin\\php\\php5.3.13\\php.ex ...
-
word排版的一些小技巧积累
先准备好样式 编辑前,可以先根据要求,设置好样式,可以免去编辑好后,再修改格式(这样要改好多文本的格式) docx doc的样式不能通用. .docx转.doc 从word2013自带的编辑公式,编辑 ...
-
SSH密钥认证添加方法和一些实用配置
更改SSH端口号 用账号密码进入主机 sudo nano /etc/ssh/sshd-config 再其中添加Port 22等或改变该条 添加公钥到主机 cd ~ sudo mkdir .ssh 此处 ...
-
30个值得关注的Vue开源项目
译者按: 学习优秀的开源项目是提高代码水平最有效的方式. 原文: 30 Amazing Vue.js Open Source Projects for the Past Year (v.2018) 译 ...
-
vue-cli使用swiper插件
使用的教程https://blog.csdn.net/lbpro0412/article/details/82465067
-
@RequestParam接收解析不到 POST 提交的 数据
1.使用postman或者其他发送请求模拟器进行模拟访问,需要指定Headers为Content-Type:application/x-www-form-urlencoded;指定body类型为x-w ...
-
flow-vue.js移动端效果
得益于vue.js和element,以及vue-element-extends在线表格编辑.前后端分离的后端用golang+beego框架,服务器采用腾讯云. vue的自适应做的很好,只要将侧栏加一行 ...