P2149 Elaxia的路线
D e s c r i p t i o n \mathrm{Description} Description
给定 n n n 个点, m m m 条边的无向图,求 2 2 2 个点对间最短路的最长公共路径
S o l u t i o n \mathrm{Solution} Solution
最短路有可能不唯一,所以公共路径的长度就有可能不同。
将 2 2 2 条最短路都会经过的边(包括同向和异向)记录出来,并建立 1 1 1 个新图,那么由于最短路(可以看做一条链)一定不会走环,故新图必定是一个 有向无环图 (简称 D A G \mathrm{DAG} DAG),而 D A G \mathrm{DAG} DAG 图上就可以跑 DP 来求解最长链,由于找出的是 2 2 2 条最短路都经过的边,所以最长链其实就是 2 2 2 条最短路的最长公共路径。文章来源:https://www.toymoban.com/news/detail-829258.html
故,该问题得以解决。文章来源地址https://www.toymoban.com/news/detail-829258.html
C o d e Code Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int SIZE = 1e6 + 10;
int N, M;
int X1, Y1, X2, Y2;
int h[SIZE], hs[SIZE], e[SIZE], ne[SIZE], w[SIZE], idx;
int D[4][SIZE], Vis[SIZE], in[SIZE], q[SIZE], hh, tt = -1;
int F[SIZE];
void add(int h[], int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}
void Dijkstra(int Start, int dist[])
{
for (int i = 1; i <= N; i ++)
dist[i] = 1e18, Vis[i] = 0;
priority_queue<PII, vector<PII>, greater<PII>> Heap;
Heap.push({0, Start}), dist[Start] = 0;
while (Heap.size())
{
auto Tmp = Heap.top();
Heap.pop();
int u = Tmp.second;
if (Vis[u]) continue;
Vis[u] = 1;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[u] + w[i])
{
dist[j] = dist[u] + w[i];
Heap.push({dist[j], j});
}
}
}
}
void Topsort()
{
hh = 0, tt = -1;
for (int i = 1; i <= N; i ++)
if (!in[i])
q[ ++ tt] = i;
while (hh <= tt)
{
int u = q[hh ++];
for (int i = hs[u]; ~i; i = ne[i])
{
int j = e[i];
if ((-- in[j]) == 0)
q[ ++ tt] = j;
}
}
}
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
memset(h, -1, sizeof h);
memset(hs, -1, sizeof hs);
cin >> N >> M >> X1 >> Y1 >> X2 >> Y2;
int u, v, c;
while (M --)
{
cin >> u >> v >> c;
add(h, u, v, c), add(h, v, u, c);
}
Dijkstra(X1, D[0]), Dijkstra(Y1, D[1]);
Dijkstra(X2, D[2]), Dijkstra(Y2, D[3]);
for (int i = 1; i <= N; i ++)
for (int j = h[i]; ~j; j = ne[j])
{
int k = e[j];
if (D[0][i] + w[j] + D[1][k] == D[0][Y1] && D[2][i] + w[j] + D[3][k] == D[2][Y2])
add(hs, i, k, w[j]), in[k] ++;
}
Topsort();
for (int it = 0; it <= tt; it ++)
{
int i = q[it];
for (int j = hs[i]; ~j; j = ne[j])
{
int k = e[j];
F[k] = max(F[k], F[i] + w[j]);
}
}
int Result = 0;
for (int i = 1; i <= N; i ++)
Result = max(Result, F[i]);
memset(hs, -1, sizeof hs);
memset(F, 0, sizeof F);
memset(in, 0, sizeof in);
for (int i = 1; i <= N; i ++)
for (int j = h[i]; ~j; j = ne[j])
{
int k = e[j];
if (D[0][i] + w[j] + D[1][k] == D[0][Y1] && D[3][i] + w[j] + D[2][k] == D[2][Y2])
add(hs, i, k, w[j]), in[k] ++;//, cout << i << " " << k << endl;
}
Topsort();
for (int it = 0; it <= tt; it ++)
{
int i = q[it];
for (int j = hs[i]; ~j; j = ne[j])
{
int k = e[j];
F[k] = max(F[k], F[i] + w[j]);
}
}
for (int i = 1; i <= N; i ++)
Result = max(Result, F[i]);
cout << Result << endl;
return 0;
}
到了这里,关于【图论经典题目讲解】洛谷 P2149 Elaxia的路线的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!