P1967 货车运输
wenge
2020-10-07 21:20:15
原题要处理连通块，但是建一个超级源点0，到其他边的边权全部设为-1，就可以避免连通块的问题，并且倍增LCA询问还不需要特判
倍增解法：
```cpp
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define clr(a,b) memset(a,b,sizeof(a))
ll n,m,q,ans;
const ll inf=-1;
struct edge{
ll u,v,w;
edge(){}
edge(ll _u,ll _v,ll _w):u(_u),v(_v),w(_w){}
}e[60005];
int cmp_edge(edge x,edge y){
return x.w>y.w;
}
ll p[10005];
ll find(ll x){
if(p[x]==x)return x;
return p[x]=find(p[x]);
}
ll merge(ll x,ll y){
x=find(x),y=find(y);
if(x!=y)p[x]=y;
}
vector<ll> F[10005],G[10005];
ll pow2[20]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384};
ll fa[10005][20],mx[10005][20],dep[10005];
void dfs1(ll x,ll z){
for(int i=0;i<F[x].size();i++){
ll y=F[x][i],w=G[x][i];
if(y==z)continue;
fa[y][0]=x,mx[y][0]=w,dep[y]=dep[x]+1;
dfs1(y,x);
}
}
ll query(ll x,ll y){
if(dep[x]<dep[y])swap(x,y);
ll delta=dep[x]-dep[y];
ll res=99999999;
for(int i=14;i>=0;i--){
if(pow2[i]<=delta){
res=min(res,mx[x][i]);
x=fa[x][i];
delta-=pow2[i];
}
}
if(x==y)return res;
for(int i=14;i>=0;i--){
if(dep[x]-pow2[i]>=0&&fa[x][i]!=fa[y][i]){
res=min(res,mx[x][i]);
res=min(res,mx[y][i]);
x=fa[x][i];
y=fa[y][i];
}
}
res=min(res,mx[x][0]);
res=min(res,mx[y][0]);
return res;
}
int main(){
//freopen("P1429_6.in","r",stdin);
//freopen("match.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
//input
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v>>e[i].w;
}
for(int i=1;i<=n;i++){
e[m+i].u=0,e[m+i].v=i,e[m+i].w=inf;
}
m+=n;
//mst
sort(e+1,e+m+1,cmp_edge);
{
for(int i=0;i<=n;i++)p[i]=i;
ll t=0;
for(int i=1;i<=m;i++){
ll u=e[i].u,v=e[i].v,w=e[i].w;
if(find(u)!=find(v)){
merge(u,v);
t++;
F[u].pb(v);
F[v].pb(u);
G[u].pb(w);
G[v].pb(w);
}
if(t==n)break;
}
}
//graph
dep[0]=0;
dfs1(0,-1);
for(int i=1;i<=14;i++){
for(int j=0;j<=n;j++){
fa[j][i]=fa[fa[j][i-1]][i-1];
mx[j][i]=min(mx[j][i-1],mx[fa[j][i-1]][i-1]);
}
}
//query
cin>>q;
while(q--){
ll u,v;
cin>>u>>v;
cout<<query(u,v)<<"\n";
}
return 0;
}
```