只有std，沒有自我實(shí)現(xiàn)，所以叫做無碼專區(qū)

description

給一張無向圖，多次詢問，每次詢問兩個點(diǎn)之間所有簡單路徑（不重復(fù)經(jīng)過點(diǎn)）中邊權(quán)第二大（不是嚴(yán)格第二大）的權(quán)值的最小值。

數(shù)據(jù)范圍：$10^5$ 級別

我的想法

前 $50\%$ 的數(shù)據(jù) $q,n\le 10^3,m\le 2\times 10^3:$

先做一次最小生成樹，求出任意兩點(diǎn)之間聯(lián)通的最小邊權(quán)（某條路徑的最大邊權(quán)值）。

每次詢問 $(u,v)$ ，我直接枚舉中間轉(zhuǎn)折點(diǎn) $i$，強(qiáng)制這條路徑是 $u\to i\to v$。【$\to$ 代指一條路徑】

第二大邊權(quán)就是 $(u,i)$ 聯(lián)通路徑的最大值和 $(v,i)$ 聯(lián)通路徑的最大值，二者中的較小值。

旁邊的 $\text{Oxide}$ 巨佬認(rèn)為很有可能 $u\to i$ 和 $i\to w$ 之間經(jīng)過了同樣的點(diǎn)。

i.e. $u\to x\to i\to x\to v$

但后面再仔細(xì)一想，就算這是的答案會被 $i$ 更新，但是后面一定會枚舉到 $x$，顯然$u\to x\to v$ 會比以前的路徑少了 $(x,i)$ 一段。

路徑上的邊權(quán)最大值一定是不減的

所以多的 $(x,i)$ 一段只可能使最大邊權(quán)增大 / 不變。

那么 $x$ 的決策一定是不劣于 $i$ 的決策的。

另有 $20\%$ 是樹：兩個點(diǎn)之間只有一條簡單路徑，可以直接倍增求路徑的第二大邊權(quán)值。

綜上，本題自我實(shí)現(xiàn)分值應(yīng)該在 $70^{\prime }$。

solution

類似最小生成樹的方法，從小到大加邊。

如果加完一條邊后，$u,v$ 之間只差一條邊聯(lián)通，那么顯然這條邊就是第二小，也就是最終的答案。

考慮怎么維護(hù)？

設(shè) $N(u):$ 與 $u$ 有直接邊相連，但還沒有相連的點(diǎn)的集合【當(dāng)前枚舉邊的權(quán)值暫時小于等于這些點(diǎn)與 $u$ 的權(quán)值，最小生成樹的寫法就還沒有加入這些邊】

或者理解為：還差一條邊就能聯(lián)通的點(diǎn)的集合

考慮啟發(fā)式合并，每次合并 $u,v$ 各自所在的連通塊。

此時可能出現(xiàn)：$N(u)$ 中的點(diǎn) $x$ 與 $v$ 相連【在 $v$ 連通塊里面】 ，或，$N(v)$ 中的點(diǎn) $y$ 與 $u$ 相連【在 $u$ 連通塊里面】

這個時候意味著，加上 $u?v$ 這條邊后，還差 $u?x$ 或 $v?y$ 這一條邊就會使得 $u,v$ 相連，所以 $u?v$ 這條邊權(quán)就是最后的答案。

如果直接枚舉 $N(u),N(v)$ 則不符合時間限制。

我們可以這么做：

• 遍歷 $N(u)$ 的所有點(diǎn)，然后看是否在 $v$ 的詢問中。

  i.e. 假設(shè) $x\in N(u),x\in q(v)$ ， $x?u$ 之間的邊還沒有加入。

  此時加入為 $u?v$ 的邊。一旦加入完，$x\to u\to v$就只差 $x?u$ 的一條邊。

  所以答案就是現(xiàn)在操作的 $u?v$ 邊的邊權(quán)。

  這樣就處理了掛在 $v$ 上面的某些 通過 $u$ 連通塊中某些點(diǎn)和邊解決 的詢問。

• 遍歷 $u$ 里面的所有詢問，判斷是否在 $N(v)$ 中。

  i.e. 假設(shè) $x\in q(u)$ ， $x?v$ 之間的邊還沒有加入。

  此時加入為 $u?v$ 的邊。一旦加入完，$x\to v\to u$ 就只差 $x?v$ 的一條邊。

  所以答案是 $u?v$ 現(xiàn)在這條邊的邊權(quán)。

  這樣就處理了掛在 $u$ 上面的某些 通過 $v$ 連通塊中某些點(diǎn)和邊解決 的詢問。

這么做會發(fā)現(xiàn)，雖然是合并兩個聯(lián)通塊和處理兩個聯(lián)通塊各自掛著的詢問，但是枚舉的只有一個聯(lián)通塊的信息。

所以啟發(fā)式合并，就用 $N(u)+q(u)$ 和 $N(v)+q(v)$ 大小比較，選較小的進(jìn)行枚舉。

時間復(fù)雜度 $O(n\log n)$

合并具體而言：枚舉其中一個較小連通塊的信息，進(jìn)行答案處理。所有掛在 $u,v$ 點(diǎn)的詢問和邊都重新掛在合并后新連通塊的根 $w$ 上。

i.e. 詢問 $u,x$ 的答案，合并后相當(dāng)于問 $w,x$ 的答案，因?yàn)榉凑?$u?w$ 的邊權(quán)不是第二大。原本 $u?x$ 的一條邊，變成 $w?x$ 的一條邊。

所以上面的形如 $x?u$ ：不一定表示原先加入的 $m$ 條邊就是 $x?u$，而是可能通過 $x?a?b?c?...?u$ ，不斷合并，可能代指的是一條簡單路徑。

參考code文章來源地址http://www.zghlxwxcb.cn/news/detail-475058.html

#include <bits/stdc++.h>
using namespace std;

#define N 400005

#define pb push_back
int fa[N];
struct node {
	int x, y, z;
} b[N];
int ans[N], n, m, Q;
set<array<int, 2>> q[N];
set<int> e[N];

int get(int x) {
	if (fa[x] == x)
		return x;
	return fa[x] = get(fa[x]);
}

inline bool cmp(node x, node y) {
	return x.z < y.z;
}

void combine(int x, int y, int val) {
	for (auto u : e[x]) {
		while (1) {
			auto it = q[y].lower_bound({u, -1});
			if (it == q[y].end() || (*it)[0] != u)
				break;
			int id = (*it)[1];
			ans[id] = val;
			assert(q[y].count({u, id}));
			assert(q[u].count({y, id}));
			q[y].erase(it);
			q[u].erase({y, id});
		}
	}
	vector<array<int, 2>> delq;
	for (auto u : q[x]) {
		if (e[y].count(u[0])) {
			ans[u[1]] = val;
			q[u[0]].erase({x, u[1]});
			delq.pb(u);
		}
	}
	for (auto u : delq)
		q[x].erase(u);
	fa[x] = y;
	for (auto v : e[x]) {
		assert(e[v].count(x));
		e[v].erase(x);
		if (v != y) {
			e[v].insert(y);
			e[y].insert(v);
		}
	}
	e[x].clear();
	for (auto v : q[x]) {
		assert(v[0] != y);
		assert(q[v[0]].count({x, v[1]}));
		q[v[0]].erase({x, v[1]});
		q[v[0]].insert({y, v[1]});
		q[y].insert({v[0], v[1]});
	}
	q[x].clear();
}

int main() {
	freopen("path.in", "r", stdin);
	freopen("path.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &Q);
	for (int i = 1; i <= n; i++)
		e[i].clear(), q[i].clear();
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].z);
		e[b[i].x].insert(b[i].y);
		e[b[i].y].insert(b[i].x);
	}
	for (int i = 1; i <= n; i++)
		fa[i] = i;
	sort(b + 1, b + 1 + m, cmp);
	for (int i = 1; i <= Q; i++) {
		ans[i] = 0;
		int x, y;
		scanf("%d%d", &x, &y);
		if (e[x].count(y)) {
			ans[i] = 1;
			continue;
		}
		q[x].insert({y, i});
		q[y].insert({x, i});
	}
	for (int i = 1; i <= m; i++) {
		b[i].x = get(b[i].x), b[i].y = get(b[i].y);
		if (b[i].x == b[i].y)
			continue;
		if (q[b[i].x].size() + e[b[i].x].size() > q[b[i].y].size() + e[b[i].y].size())
			swap(b[i].x, b[i].y);
		combine(b[i].x, b[i].y, b[i].z + 1);
	}
	for (int i = 1; i <= Q; i++)
		printf("%d\n", ans[i] - 1);
}

到了這里，關(guān)于【無碼專區(qū)1】簡單路徑的第二大邊權(quán)（啟發(fā)式合并+最小生成樹)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！