P2149 Elaxia的路線

D e s c r i p t i o n \mathrm{Description} Description

給定 $n$ 個(gè)點(diǎn)，$m$ 條邊的無向圖，求 $2$ 個(gè)點(diǎn)對(duì)間最短路的最長(zhǎng)公共路徑

S o l u t i o n \mathrm{Solution} Solution

最短路有可能不唯一，所以公共路徑的長(zhǎng)度就有可能不同。

將 $2$ 條最短路都會(huì)經(jīng)過的邊（包括同向和異向）記錄出來，并建立 $1$ 個(gè)新圖，那么由于最短路（可以看做一條鏈）一定不會(huì)走環(huán)，故新圖必定是一個(gè) 有向無環(huán)圖 （簡(jiǎn)稱 $\mathrm{DAG}$），而 $\mathrm{DAG}$ 圖上就可以跑 DP 來求解最長(zhǎng)鏈，由于找出的是 $2$ 條最短路都經(jīng)過的邊，所以最長(zhǎng)鏈其實(shí)就是 $2$ 條最短路的最長(zhǎng)公共路徑。

故，該問題得以解決。文章來源地址http://www.zghlxwxcb.cn/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;
}

到了這里，關(guān)于【圖論經(jīng)典題目講解】洛谷 P2149 Elaxia的路線的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！