做手机网站公司,怎么建设网站,保定网站建设找谁,php自助建站程序只有std#xff0c;没有自我实现#xff0c;所以叫做无码专区
description
给一张无向图#xff0c;多次询问#xff0c;每次询问两个点之间所有简单路径#xff08;不重复经过点#xff09;中边权第二大#xff08;不是严格第二大#xff09;的权值的最小值。
数据…只有std没有自我实现所以叫做无码专区
description
给一张无向图多次询问每次询问两个点之间所有简单路径不重复经过点中边权第二大不是严格第二大的权值的最小值。
数据范围10510^5105 级别
我的想法
前 50%50\%50% 的数据 q,n≤103,m≤2×103:q,n\le 10^3,m\le 2\times 10^3:q,n≤103,m≤2×103:
先做一次最小生成树求出任意两点之间联通的最小边权某条路径的最大边权值。
每次询问 (u,v)(u,v)(u,v) 我直接枚举中间转折点 iii强制这条路径是 u→i→vu\rightarrow i\rightarrow vu→i→v。【→\rightarrow→ 代指一条路径】
第二大边权就是 (u,i)(u,i)(u,i) 联通路径的最大值和 (v,i)(v,i)(v,i) 联通路径的最大值二者中的较小值。
旁边的 Oxide\text{Oxide}Oxide 巨佬认为很有可能 u→iu\rightarrow iu→i 和 i→wi\rightarrow wi→w 之间经过了同样的点。
i.e. u→x→i→x→vu\rightarrow x\rightarrow i \rightarrow x\rightarrow vu→x→i→x→v
但后面再仔细一想就算这是的答案会被 iii 更新但是后面一定会枚举到 xxx显然u→x→vu\rightarrow x\rightarrow vu→x→v 会比以前的路径少了 (x,i)(x,i)(x,i) 一段。
路径上的边权最大值一定是不减的
所以多的 (x,i)(x,i)(x,i) 一段只可能使最大边权增大 / 不变。
那么 xxx 的决策一定是不劣于 iii 的决策的。
另有 20%20\%20% 是树两个点之间只有一条简单路径可以直接倍增求路径的第二大边权值。
综上本题自我实现分值应该在 70′7070′。
solution
类似最小生成树的方法从小到大加边。
如果加完一条边后u,vu,vu,v 之间只差一条边联通那么显然这条边就是第二小也就是最终的答案。
考虑怎么维护
设 N(u):N(u):N(u): 与 uuu 有直接边相连但还没有相连的点的集合【当前枚举边的权值暂时小于等于这些点与 uuu 的权值最小生成树的写法就还没有加入这些边】
或者理解为还差一条边就能联通的点的集合
考虑启发式合并每次合并 u,vu,vu,v 各自所在的连通块。
此时可能出现N(u)N(u)N(u) 中的点 xxx 与 vvv 相连【在 vvv 连通块里面】 或N(v)N(v)N(v) 中的点 yyy 与 uuu 相连【在 uuu 连通块里面】
这个时候意味着加上 u−vu-vu−v 这条边后还差 u−xu-xu−x 或 v−yv-yv−y 这一条边就会使得 u,vu,vu,v 相连所以 u−vu-vu−v 这条边权就是最后的答案。
如果直接枚举 N(u),N(v)N(u),N(v)N(u),N(v) 则不符合时间限制。
我们可以这么做 遍历 N(u)N(u)N(u) 的所有点然后看是否在 vvv 的询问中。 i.e. 假设 x∈N(u),x∈q(v)x\in N(u),x\in q(v)x∈N(u),x∈q(v) x−ux-ux−u 之间的边还没有加入。 此时加入为 u−vu-vu−v 的边。一旦加入完x→u→vx\rightarrow u\rightarrow vx→u→v就只差 x−ux-ux−u 的一条边。 所以答案就是现在操作的 u−vu-vu−v 边的边权。 这样就处理了挂在 vvv 上面的某些 通过 uuu 连通块中某些点和边解决 的询问。 遍历 uuu 里面的所有询问判断是否在 N(v)N(v)N(v) 中。 i.e. 假设 x∈q(u)x\in q(u)x∈q(u) x−vx-vx−v 之间的边还没有加入。 此时加入为 u−vu-vu−v 的边。一旦加入完x→v→ux\rightarrow v\rightarrow ux→v→u 就只差 x−vx-vx−v 的一条边。 所以答案是 u−vu-vu−v 现在这条边的边权。 这样就处理了挂在 uuu 上面的某些 通过 vvv 连通块中某些点和边解决 的询问。
这么做会发现虽然是合并两个联通块和处理两个联通块各自挂着的询问但是枚举的只有一个联通块的信息。
所以启发式合并就用 N(u)q(u)N(u)q(u)N(u)q(u) 和 N(v)q(v)N(v)q(v)N(v)q(v) 大小比较选较小的进行枚举。
时间复杂度 O(nlogn)O(n\log n)O(nlogn)
合并具体而言枚举其中一个较小连通块的信息进行答案处理。所有挂在 u,vu,vu,v 点的询问和边都重新挂在合并后新连通块的根 www 上。
i.e. 询问 u,xu,xu,x 的答案合并后相当于问 w,xw,xw,x 的答案因为反正 u−wu-wu−w 的边权不是第二大。原本 u−xu-xu−x 的一条边变成 w−xw-xw−x 的一条边。
所以上面的形如 x−ux-ux−u 不一定表示原先加入的 mmm 条边就是 x−ux-ux−u而是可能通过 x−a−b−c−...−ux-a-b-c-...-ux−a−b−c−...−u 不断合并可能代指的是一条简单路径。
参考code
#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;
setarrayint, 2 q[N];
setint 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});}}vectorarrayint, 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);
}
