经典图论
例题
P6833 [Cnoi2020] 雷雨
枚举三条路径交,求最小值即可。
最短路树
按松弛操作记录一个点的前驱,将前驱作为父亲建树。
性质
- 形态不唯一
- 根节点到其他所有点的最短距离与原图中相同
- 在所有生成树中,最短路径树满足根节点到其他所有点的距离之和最短
例题
P5201 [USACO19JAN] Shortcut G
在最短路树上考虑问题,那么问题转化为求 \(\max \{ (dis_i - T) \times sz_i \}\)。
题目要求最短路的字典序最小,在记录最短路前驱的时候顺便维护即可。
代码:
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;const int N = 1e4 + 5;
int n, m, t, u, v, w, ans, a[N], sz[N], fa[N], dis[N];
bool vis[N];
struct Node {int v, w;
} ;
vector<int> G[N];
vector<Node> g[N];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;inline void dijkstra(int s) {fill(dis + 1, dis + 1 + n, 1e18);dis[s] = 0;q.push({0ll, s});while(! q.empty()) {auto [_, u] = q.top();q.pop();if(vis[u]) continue ;vis[u] = true;for(auto [x, w] : g[u]) {if(dis[u] + w < dis[x]) {fa[x] = u;dis[x] = dis[u] + w;q.push({dis[x], x});}else if(dis[u] + w == dis[x]) fa[x] = min(fa[x], u);}}return ;
}inline void dfs(int x, int last) {sz[x] = a[x];for(auto u : G[x])if(u != last) {dfs(u, x);sz[x] += sz[u];}ans = max(ans, (dis[x] - t) * sz[x]);return ;
}signed main() {ios_base :: sync_with_stdio(NULL);cin.tie(nullptr);cout.tie(nullptr);cin >> n >> m >> t;for(int i = 1 ; i <= n ; ++ i)cin >> a[i]; for(int i = 1 ; i <= m ; ++ i) {cin >> u >> v >> w;g[u].pb({v, w}), g[v].pb({u, w});}dijkstra(1);for(int i = 1 ; i <= n ; ++ i)G[i].pb(fa[i]), G[fa[i]].pb(i);dfs(1, -1);cout << ans;return 0;
}