Bond
题目链接
Bond
给定一张 \(n\) 个点 \(m\) 条边的无向图，每条边有一个权值，有 \(q\) 个询问，每次询问给出两个点 \((s,t)\)，找到从一条从 \(s\) 到 \(t\) 的路径，使得最大权值最小，只需输出这个权值
解题思路
最小生成树，ST，树链剖分，并查集按秩合并，最小瓶颈生成树
首先，可以肯定一点，这条路径一定可以是最小生成树上的一条唯一路径
定理：最小生成树是最小瓶颈生成树，但是最小瓶颈生成树不一定是最小生成树
可利用 kruskal 算法求出最小生成树，再利用和 \(CLA\) 类似的思想求出最小生成树上两点之间的最大权值，或者求树上两点之间的最大值可利用树链剖分（树链剖分只是一种思想，可用线段树或 \(st\) 表来实现）来求，或者可以用 tarjan 离线求解
当然，在利用并查集求最小生成树时可以按秩合并，这样整棵树的高度为 \(O(logn)\) 级别，这样只需要从 \(s\) 开始回溯并记录到该节点的最大值，然后从 \(t\) 开始回溯，如果遇到标记，该标记如果为根节点，说明两个点不在一条链上，则取记录到该节点的较大值；否则在一条链上仍取较大值，因为如果 \(t\) 位于 \(s\) 下面，遇到标记时说明 \(t\) 到 \(s\) 的路径已经走过了，否则如果 \(t\) 位于 \(s\) 上面，则一开始就回溯，答案即为到 \(t\) 的最大值
\(\color{red}{并查集按秩合并虽然没破坏树形结构，但最后形成的树也不是最小生成树，为什么可以直接按最小生成树操作？}\)
由于边权是按从小到大排序的，每次合并时大的边权都集中在深度较低的位置，由于计算的是最大权值，即使向上回溯时有些边权没有统计到，但大的边权一定会统计到，所以不会对答案造成影响
- 时间复杂度：\(O(mlogm+qlogn)\)
tarjan：
- 时间复杂度：\(O(mlogm+q)\)
树链剖分（线段树）:
- 时间复杂度：\(O(mlogm+qlog^2n)\)
代码
- tarjan
// Problem: Bond
// Contest: Virtual Judge - UVA
// URL: https://vjudge.net/problem/UVA-11354
// Memory Limit: 1024 MB
// Time Limit: 8000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair PII;
typedef pair PLL;
template bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=5e4+5,M=1e5+5;
int n,m,q,h[N],fa[N],up[N],res[M],w[N];
vector adj[N];
vector query[N];
PII ask[M];
vector ids[N];
bool vis[N];
struct A
{
int x,y,w;
bool operator<(const A &o)
{
return w=n-1)break;
}
}
void add_query(int u,int v,int id)
{
query[u].emplace_back(v,id);
query[v].emplace_back(u,id);
}
void tarjan(int u,int father)
{
up[u]=0;
for(auto t:adj[u])
{
int v=t.fi,w=t.se;;
if(v==father)continue;
tarjan(v,u);
up[v]=w;
fa[v]=u;
}
vis[u]=true;
for(auto t:query[u])
{
int v=t.fi,id=t.se;
if(vis[v])
ids[get(v)].pb(id);
}
for(int id:ids[u])
{
int u=ask[id].fi,v=ask[id].se;
get(u),get(v);
res[id]=max(up[u],up[v]);
}
}
int main()
{
help;
bool f=false;
while(cin>>n>>m)
{
if(f)puts("");
f=true;
for(int i=1;i<=n;i++)
fa[i]=i,ids[i].clear(),adj[i].clear(),query[i].clear(),up[i]=vis[i]=h[i]=0;
for(int i=1;i<=m;i++)cin>>a[i].x>>a[i].y>>a[i].w;
kruskal();
for(int i=1;i<=n;i++)fa[i]=i;
cin>>q;
for(int i=1;i<=q;i++)
{
cin>>ask[i].fi>>ask[i].se;
add_query(ask[i].fi,ask[i].se,i);
}
tarjan(1,0);
for(int i=1;i<=q;i++)
{
cout< - ST+并查集路径压缩+按秩合并（高度）
// Problem: Bond
// Contest: Virtual Judge - UVA
// URL: https://vjudge.net/problem/UVA-11354
// Memory Limit: 1024 MB
// Time Limit: 8000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include
// #define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair PII;
typedef pair PLL;
template bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=5e4+5,M=1e5+5;
int n,m,q,s,t,tt,fa[N],h[N],d[N],f[N][20],mx[N][20];
vector adj[N];
struct A
{
int a,b,w;
bool operator<(const A &o)
{
return w=n-1)break;
}
}
void bfs()
{
queue q;
q.push(1);
d[1]=1;
while(q.size())
{
int x=q.front();
q.pop();
for(auto t:adj[x])
{
int y=t.fi,w=t.se;
if(d[y])continue;
d[y]=d[x]+1;
f[y][0]=x;
mx[y][0]=w;
for(int i=1;i<=tt;i++)f[y][i]=f[f[y][i-1]][i-1],mx[y][i]=max(mx[y][i-1],mx[f[y][i-1]][i-1]);
q.push(y);
}
}
}
int LCA(int x,int y)
{
if(d[x]=0;i--)
if(d[f[x][i]]>=d[y])res=max(res,mx[x][i]),x=f[x][i];
if(x==y)return res;
for(int i=tt;i>=0;i--)
if(f[x][i]&&f[x][i]!=f[y][i])res=max({res,mx[x][i],mx[y][i]}),x=f[x][i],y=f[y][i];
return max({res,mx[x][0],mx[y][0]});
}
int main()
{
help;
int T=0;
while(cin>>n>>m)
{
for(int i=1;i<=n;i++)adj[i].clear(),h[i]=d[i]=0;
if(T)puts("");
T++;
tt=log(n)/log(2);
for(int i=1;i<=m;i++)cin>>a[i].a>>a[i].b>>a[i].w;
for(int i=1;i<=n;i++)fa[i]=i;
kruskal();
bfs();
cin>>q;
while(q--)
{
cin>>s>>t;
cout< - 树链剖分（线段树）
// Problem: Bond
// Contest: Virtual Judge - UVA
// URL: https://vjudge.net/problem/UVA-11354
// Memory Limit: 1024 MB
// Time Limit: 8000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair PII;
typedef pair PLL;
template bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=5e4+5,M=1e5+5;
int n,m,x,y,d,q,s,t,fa[N],cnt,sz[N],son[N],pa[N],dep[N],top[N],nw[N],fw[N],id[N];
vector adj[N];
struct A
{
int x,y,w;
bool operator<(const A &o)
{
return w<=o.w;
}
}a[M];
struct T
{
int l,r;
int mx;
}tr[4*N];
void pushup(int u)
{
tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);
}
void build(int u,int l,int r)
{
tr[u]={l,r,0};
if(l==r)
{
tr[u].mx=nw[l];
return ;
}
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
int ask(int u,int l,int r)
{
if(l<=tr[u].l&&tr[u].r<=r)return tr[u].mx;
int res=0;
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid)res=max(res,ask(u<<1,l,r));
if(r>mid)res=max(res,ask(u<<1|1,l,r));
return res;
}
int ask_path(int u,int v)
{
int res=0;
while(top[u]!=top[v])
{
if(dep[top[u]]dep[v])swap(u,v);
res=max(res,ask(1,id[son[u]],id[v]));
return res;
}
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void kruskal()
{
sort(a+1,a+1+m);
for(int i=1;i<=m;i++)
{
int x=a[i].x,y=a[i].y,w=a[i].w;
int tx=x,ty=y;
x=find(x),y=find(y);
if(x!=y)
{
fa[x]=y;
adj[tx].pb({ty,w}),adj[ty].pb({tx,w});
}
}
}
void dfs(int x,int fa,int depth)
{
sz[x]=1,pa[x]=fa,dep[x]=depth,son[x]=0;
for(auto t:adj[x])
{
int y=t.fi;
if(y==fa)continue;
fw[y]=t.se;
dfs(y,x,depth+1);
sz[x]+=sz[y];
if(sz[son[x]]>q;
while(q--)
{
scanf("%d%d",&s,&t);
printf("%d\n",ask_path(s,t));
}
}
return 0;
}
- 树链剖分（st表）
// Problem: Bond
// Contest: Virtual Judge - UVA
// URL: https://vjudge.net/problem/UVA-11354
// Memory Limit: 1024 MB
// Time Limit: 8000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair PII;
typedef pair PLL;
template bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=5e4+5,M=1e5+5;
int n,m,q,s,t,st[N][20],id[N],idx,sz[N],h[N],top[N],dep[N],son[N],fa[N],tt;
vector adj[N];
int find(int x)
{
return x==fa[x]?x:fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
if(h[x]=n-1)break;
}
}
void dfs(int x)
{
sz[x]=1;
son[x]=0;
for(auto t:adj[x])
{
int y=t.fi;
if(y==fa[x])continue;
dep[y]=dep[x]+1;
fa[y]=x;
dfs(y);
sz[x]+=sz[y];
if(sz[son[x]]dep[v])swap(u,v);
res=max(res,ask_st(id[son[u]],id[v]));
return res;
}
int main()
{
help;
bool f=false;
while(cin>>n>>m)
{
if(f)puts("");
f=true;
for(int i=1;i<=n;i++)adj[i].clear(),fa[i]=i;
for(int i=1;i<=m;i++)cin>>a[i].x>>a[i].y>>a[i].w;
tt=log(n)/log(2);
kruskal();
fa[1]=0;
dep[1]=1;
dfs(1);
idx=0;
dfs(1,1);
for(int j=1;j<=tt;j++)
for(int i=1;i+(1<>q;
while(q--)
{
cin>>s>>t;
cout< - 并查集按秩合并（大小）
// Problem: Bond
// Contest: Virtual Judge - UVA
// URL: https://vjudge.net/problem/UVA-11354
// Memory Limit: 1024 MB
// Time Limit: 8000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair PII;
typedef pair PLL;
template bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=5e4+5,M=1e5+5;
int n,m,x,y,d,q,s,t,fa[N],sz[N],e[N],vis[N];
struct A
{
int x,y,w;
bool operator<(const A &o)
{
return w<=o.w;
}
}a[M];
int find(int x)
{
return fa[x]==x?x:find(fa[x]);
}
void merge(int x,int y,int w)
{
if(sz[x]>n>>m)
{
if(f)puts("");
f=true;
for(int i=1;i<=m;i++)cin>>a[i].x>>a[i].y>>a[i].w;
for(int i=0;i<=n;i++)fa[i]=i,sz[i]=1;
kruskal();
cin>>q;
while(q--)
{
cin>>s>>t;
solve(s,t);
}
}
return 0;
}