P1967 [NOIP2013 提高组] 货车运输 题解
P1967 [NOIP2013 提高组] 货车运输
思路:
由于题目要求的是使两点之间的最小边权最大,所以可以构造最大生成树(最大生成树一定是最大瓶颈生成树,而瓶颈生成树上两点之间的路径,在原图中的所有路径中,最小边权仍然最大,即满足题目要求,详见 https://oi-wiki.org/graph/mst/#性质 ),答案为最大生成树上的路径的最小边权。
求树上路径上的边权最值可以使用 \(LCA\),因为它可以通过合并两个点的 \(LCA\) 和这两个点到 \(LCA\) 的路径的边权最值得来。
做法:
先用 \(Kruskal\) 算出最大生成树,再用倍增的方式计算 \(LCA\),并维护每条路径上的最小边权。
\(e\) 表示初始图,\(G\) 表示最大生成树,\(deep\) 表示点的深度,\(fa_{i,j}\) 表示 \(i\) 的第 \(2^j\) 级祖先,\(w_{i,j}\) 表示 \(i\) 到 \(i\) 的第 \(2^j\) 级祖先的路径上的最小边权,在求 \(LCA\) 的过程中输出经过的点上的最小边权即可。
代码:
时间复杂度:\(\Theta(m\log m + n\log n)\)
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
const int N = 10010;
const int E = 50010;
const int M = 25;
const int INF = 1e18;
struct Node { int v, w; } ;
struct Edge { int u, v, w; } ;
int n, m, q;
int f[N], fa[N][M], deep[N], w[N][M];
bool vis[N];
Edge e[E];
vector<Node> G[N];
// 排序初始边,用于求最大生成树
bool cmpk(Edge x, Edge y) { return x.w > y.w; }
int find(int x) // 并查集 - 查找祖先
{
if(f[x] == x)
return f[x];
return f[x] = find(f[x]);
}
void kruskal() // 求最大生成树
{
sort(e+1, e+m+1, cmpk);
for(int i=1; i<=n; i++)
f[i] = i;
for(int i=1; i<=m; i++)
{
int u = e[i].u, v = e[i].v, w = e[i].w;
if(find(u) == find(v))
continue;
f[find(u)] = find(v);
G[u].push_back({v, w});
G[v].push_back({u, w});
}
}
void predfs(int u) // LCA初始化1 - 求出深度、父亲
{
vis[u] = true;
for(int i=0; i<G[u].size(); i++)
{
int v = G[u][i].v;
if(vis[v])
continue;
deep[v] = deep[u] + 1;
fa[v][0] = u;
w[v][0] = G[u][i].w;
predfs(v);
}
}
int LCA(int x, int y) // 求LCA和答案
{
if(find(x) != find(y))
return -1;
int ans = INF;
if(deep[x] > deep[y])
swap(x, y);
for(int i=20; i>=0; i--)
{
if(deep[fa[y][i]] < deep[x])
continue;
ans = min(ans, w[y][i]);
y = fa[y][i];
}
if(x == y)
return ans;
for(int i=20; i>=0; i--)
{
if(fa[x][i] == fa[y][i])
continue;
ans = min(ans, min(w[x][i], w[y][i]));
x = fa[x][i];
y = fa[y][i];
}
ans = min(ans, min(w[x][0], w[y][0]));
return ans;
}
void prelca() // LCA初始化2 - 求出祖先
{
for(int i=1; i<=20; i++)
{
for(int j=1; j<=n; j++)
{
fa[j][i] = fa[fa[j][i-1]][i-1];
w[j][i] = min(w[j][i-1], w[fa[j][i-1]][i-1]);
}
}
}
signed main()
{
cin >> n >> m;
for(int i=1; i<=m; i++)
cin >> e[i].u >> e[i].v >> e[i].w;
kruskal();
for(int i=1; i<=n; i++)
{
if(vis[i])
continue;
deep[i] = 1;
predfs(i);
fa[i][0] = i;
w[i][0] = INF;
}
prelca();
cin >> q;
while(q --)
{
int x, y; cin >> x >> y;
cout << LCA(x, y) << '\n';
}
return 0;
}
热门相关:恶魔总裁霸道宠:老婆,太惹火 纣临 神秘复苏 九星毒奶 美食萌后:皇上,休了你