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(mlog m + nlog n))
#include
#include
#include
#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 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 deep[y])
swap(x, y);
for(int i=20; i>=0; i--)
{
if(deep[fa[y][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> n >> m;
for(int i=1; i> e[i].u >> e[i].v >> e[i].w;
kruskal();
for(int i=1; i> q;
while(q --)
{
int x, y; cin >> x >> y;
cout
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net