原題鏈接:貨車運輸
kruskal重構樹+LCA做法,樹剖不想寫
很容易發現原圖跑最短路可以解,但是復雜度難以承受,所以考慮如何簡化該圖。
發現原圖邊權維護的應該是(u,v)的最小值,并且最優選擇是這個最小值最大,所以如果有多條(u,v),只保留最大的沒有影響,如果我們維護一棵最大生成樹就一定包含(u,v)的最優解。這一部分可以用kruskal重構樹。
然后考慮對于這棵樹,如何求(u,v)路徑上的最小值。
對于一棵樹(u,v)是確定的唯一路徑,我們可以發現可以把(u,v)拆成兩條從LCA(u,v)到u和v的鏈,最后對它們取min。暴力的做法可以從u,分別上跳直到找到LCA(u,v),時間復雜度O(n),難以承受,所以用倍增LCA,同時維護一個數組st,st[i][j]表示i節點到i的2j輩祖宗節點這條鏈的min,我們在求min((i,LCA))時,發現可以通過類似LCA算法中將x,y深度拉平的方法,不斷上跳使i逼近LCA,期間用每一條短鏈更新答案,最終求出min((i,LCA)),最后合并兩條鏈答案即可。時間復雜度O(nlogn),可以接受。
AC代碼:
點擊查看代碼
#include<bits/stdc++.h>
using namespace std;
int const N=1e4+10,M=5e4+10;
int p[N];
struct node{
int u,v;
int w;
bool flag;
}tree[M];
int h[N],nx[M],to[M],vl[M],idx=1;
int n,m;
int deep[N],st[N][21],anst[N][21];
bool cmp(node a,node b)
{
return a.w>b.w;
}
int find(int x)
{
if(p[x]==x) return x;
p[x]=find(p[x]);
return p[x];
}
void kruskal(){
for(int i=1;i<=n;i++) p[i]=i;
sort(tree+1,tree+m+1,cmp);
for(int i=1;i<=m;i++)
{
int u=tree[i].u,v=tree[i].v;
int root1=find(u),root2=find(v);
if(root1!=root2)
{
p[root1]=root2;
tree[i].flag=1;
}
}
}
inline void add(int u,int v,int w)
{
to[idx]=v;
nx[idx]=h[u];
vl[idx]=w;
h[u]=idx++;
}
void dfs(int u,int fa)
{
if(u==0) anst[u][0]=0;
else anst[u][0]=fa;
if(u==0) deep[u]=0;
else deep[u]=deep[fa]+1;
//預處理祖先節點,st數組
for(int i=h[u];i;i=nx[i])
{
int v=to[i],w=vl[i];
if(v==fa) continue;
st[v][0]=w;
dfs(v,u);
}
}
void first()//LCA算法的預處理
{
for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;i<=n;i++)
{
anst[i][j]=anst[anst[i][j-1]][j-1];
}
}
}
int lca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
int d=deep[x]-deep[y];
for(int i=0;(1<<i)<=d;i++)
{
if((1<<i) & d)
x=anst[x][i];
}
if(x==y) return x;
for(int i=20;i>=0;i--)
{
if(anst[x][i]!=anst[y][i])
{
x=anst[x][i];
y=anst[y][i];
}
if(anst[x][0]==anst[y][0]) break;
}
return anst[x][0];
}
void RMQ()//預處理st數組
{
for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;i<=n;i++)
{
st[i][j]=min(st[i][j-1],st[anst[i][j-1]][j-1]);
}
}
}
int check(int fa,int v)//計算子節點到LCA的一條鏈的min
{
int d=deep[v]-deep[fa];
int mn=INT_MAX;
for(int j=0;(1<<j)<=d;j++)
{
if((1<<j) & d)
{
mn=min(mn,st[v][j]);
v=anst[v][j];
}
}
return mn;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
tree[i].u=u;
tree[i].v=v;
tree[i].w=w;
}
kruskal();
for(int i=1;i<=m;i++)
{
if(!tree[i].flag) continue;
int u=tree[i].u,v=tree[i].v,w=tree[i].w;
add(u,v,w);
add(v,u,w);
}
for(int i=1;i<=n;i++)
{
if(p[i]==i) add(0,i,0);
}//可能是森林,所以需要建立虛擬節點連接,方便DFS
dfs(0,-1);
first();
RMQ();
int q;
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
int x,y;
scanf("%d%d",&x,&y);
int fa=lca(x,y);
if(fa==0) cout<<-1<<endl;//如果LCA是虛擬節點就說明不連通
else printf("%d\n",min(check(fa,x),check(fa,y)));
}
return 0;
}
碼字不易,求贊qwq(轉載請標明出處)。
浙公網安備 33010602011771號