货车运输

A国有n座城市，编号从 1到n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

对于这道题，容易想到的是一个朴素的算法。即用跑最短路的思路来跑出最小值最大的一条路，只需对spfa进行稍许修改即可。

if(min(d[x],son.w)>d[son.v])
    d[son.v]=min(d[x],son.w);

这种算法是基于最小值最大的路也有和最短/最长路一样的特性，满足三角形不等式，故必然可以用spfa跑。

朴素算法可以得30分。

另一种思想是考虑我们要找的是最小值最大的一条路，这满足二分的性质，具有单调性。但是进一步思考，检验一个解的复杂度也是搜索级别的，二分没有意义。

我们再来仔细想想这个问题本身，一些容量很低的边并且可以不被经过的边是没有意义的，是可以删掉的。按照这个思路，我们其实只需要一颗能尽量把所有点连起来的树，这颗树内的边容量尽量大，那我们只需跑一遍kruskal找最大生成树即可。

到这一步，问题就从图上转化成在森林上了，而森林上的问题几乎都可以在树上解决。

首先判断连通性，这一步很简单，用并查集即可，而且前面的kruskal就维护了并查集了。

若具有连通性，那么这两点一定位于同一颗树内，找这条路径上的边权最小值即可。暴力的复杂度还是很高，我们无法接受。但这个过程明显可以用倍增优化。构造一个数组存每个点第2^i祖先即可。合并时按照二进制拆分的思想进行。这个过程与LCA完全相同，在LCA模板上加入这个数组即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
const int inf=INT_MAX;
int n,m;
int x,y,c;
int qs;
struct edge{
    int v,w,from;
    edge(int a=0,int b=0,int c=0){
        from=a;v=b;w=c;
    }
};

vector<edge> g[maxn];
edge ed[5*maxn];
int dad[5*maxn];
int tot;
int f[maxn][20];
int w[maxn][20];
int dep[maxn];

int find(int x){
    if(dad[x]==x)return x;
    return dad[x]=find(dad[x]);
}

bool cmp(edge a,edge b){
    return a.w>b.w;
}

void kru(){
    sort(ed+1,ed+m+1,cmp);
    for (int i=1;i<=m;i++){
        int xx=ed[i].from;int yy=ed[i].v;
        if(find(xx)!=find(yy)){
            g[xx].push_back(edge(xx,yy,ed[i].w));
            g[yy].push_back(edge(yy,xx,ed[i].w));
            dad[find(xx)]=dad[find(yy)];
        }
    }
}

void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for (int i=1;i<=19;i++){ //这里正反很重要！ 
        f[u][i] = f[f[u][i-1]][i-1];
        w[u][i] = min(w[u][i-1],w[f[u][i-1]][i-1]);
    }
    for (int i=0;i<g[u].size();i++){
        if(g[u][i].v==fa)continue;
        w[g[u][i].v][0] = g[u][i].w;
        dfs(g[u][i].v,u);
    }
}

int lca(int x,int y){
    int ans=inf;
    if(dep[x]<dep[y])swap(x,y);
    for (int i=19;i>=0;i--){
        if(dep[f[x][i]]>=dep[y]){
            ans=min(ans,w[x][i]);x=f[x][i];
        }
    }
    if(x==y)return ans;
    for (int i=19;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            ans = min(ans,w[x][i]);
            ans = min(ans,w[y][i]);
            x=f[x][i];y=f[y][i];
        }
    }
    ans = min(ans,w[x][0]);ans = min(ans,w[y][0]);
    return ans;
}



int main(){
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        cin>>x>>y>>c;
        ed[++tot] = edge(x,y,c);
        dad[i]=i;
    }
    for (int i=1;i<=n;i++)dad[i]=i;
    kru();
    dfs(1,0);
    for (int i=1;i<=n;i++){
        if(dep[i]==0){
            dfs(i,0);
        }
    }
    //for (register int j=19;j>=1;j--)
    //    for (register int i=1;i<=n;++i){
    //        f[i][j]=f[f[i][j-1]][j-1];
    //        w[i][j]=min(w[i][j-1],w[f[i][j-1]][j-1]);
    //    }
    cin>>qs;
    for (int i=1;i<=qs;i++){
        cin>>x>>y;
        if(find(x)!=find(y)){
        	cout<<-1<<endl;continue;
        }
        cout<<lca(x,y)<<endl;
    }
    return 0;
}

下面这是直接套kruskal重构树的板子写的。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
const int inf=INT_MAX;
int n,m;
int x,y,c;
int qs;
struct edge{
    int v,w,from;
    edge(int a=0,int b=0,int c=0){
        from=a;v=b;w=c;
    }
};

vector<edge> g[4*maxn];
edge ed[5*maxn];
int dad[5*maxn];
int tot;
int f[maxn][20];
int dep[maxn];
int d[2*maxn];
int t;

int find(int x){
	if(dad[x]==x)return x;
	return dad[x]=find(dad[x]);
}

bool cmp(edge a,edge b){
	return a.w>b.w;
}

void kru(){
	sort(ed+1,ed+m+1,cmp);
	for (int i=1;i<=m;i++){
		int xx=ed[i].from;int yy=ed[i].v;
		if(find(xx)!=find(yy)){
			d[++t] = ed[i].w;
			g[t].push_back(edge(t,find(yy),0));
			g[find(yy)].push_back(edge(find(yy),t,0));
			g[t].push_back(edge(t,find(xx),0));
			g[find(xx)].push_back(edge(find(xx),t,0));
			dad[find(xx)]=dad[find(yy)]=dad[t]=t;//这里 
		}
	}
}

void dfs(int u,int fa){
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	for (int i=1;i<=19;i++){
	    f[u][i] = f[f[u][i-1]][i-1];
	}
	for (int i=0;i<g[u].size();i++){
		if(g[u][i].v==fa)continue;
		dfs(g[u][i].v,u);
	}
}

int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for (int i=19;i>=0;i--){
		if(dep[f[x][i]]>=dep[y]){
			x=f[x][i];
		}
	}
	if(x==y)return x;
	for (int i=19;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			x=f[x][i];y=f[y][i];
		}
	}
	return f[x][0];
}



int main(){
    cin>>n>>m;
    t=n;
    for (int i=1;i<=m;i++){
        cin>>x>>y>>c;
        ed[++tot] = edge(x,y,c);
        dad[i]=i;
    }
    for (int i=1;i<=n;i++)dad[i]=i;
    kru();
	dfs(t,0);
	for (int i=1;i<=n;i++){
		if(dep[i]==0){
		    dfs(find(i),0);
		}
	}
    cin>>qs;
    for (int i=1;i<=qs;i++){
        cin>>x>>y;
        if(find(x)!=find(y)){
        	cout<<-1<<endl;continue;
		}
        cout<<d[lca(x,y)]<<endl;
    }
    return 0;
}