LuoguP1967货车运输。

题目描述

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

输入输出格式

输入格式

第一行有两个用一个空格隔开的整数 $n,m$，表示 $A$ 国有 $n$ 座城市和$m$条道路。

接下来$m$行每行$3$个整数 $x, y, z$，每两个整数之间用一个空格隔开，表示从$x$号城市到$y$号城市有一条限重为$z$的道路。注意:$x$ 不等于 $y$，两座城市之间可能有多条道路。

接下来一行有一个整数 $q$，表示有$q$ 辆货车需要运货。

接下来 $q$ 行，每行两个整数$ x,y$，之间用一个空格隔开，表示一辆货车需要从 $x$ 城市运输货物到 $y$ 城市，注意： $x$ 不等于 $y$。

输出格式

共有 $q$ 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出$-1$。

INPUT & OUTPUT’s examples

Input’s e.g. #1

Output’s e.g. #1

1
2
3

3
-1
3

分析

首先看完题我们就能想到Floyd最长路的算法,时间复杂度$O(n^3)$.

我们设一个$weight$数组来表示最大载重,状态转移方程式也不难推出，为:

$$w_{i,j} = max(w_{i,j},min(w_{i,k},w_{k,j}))$$

开始考虑优化：

我们可以发现，很多权值较小的边绝对不在我们的考虑范围内，所以我们可以将它们去掉。

因为我们要求走过的边权尽可能大，所以我们可以构建一棵最大生成树。

现在有了这样一棵最大生成树，我们就要考虑如何求出两个节点之间的最小边权的最大值。

因为树上的两个节点之间只有唯一的一条路径，所以我们就可以求出这两个点的最近公共祖先(这里我们用树上倍增实现)

此题代码实现难度和思考难度均较大（对于Herself32这种菜鸡来说），是一道不错的图论进阶题目。

代码

/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*its=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==its)
            its=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==its)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        }
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(int inner){
    	if(inner == 0)puts("");
    	else putchar(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(0);
}
/* definitions */
const int MAXN = 5e4 + 1;
const int MAXB = 20 + 1;
int n,m;
struct Edge{
    int from,to,val;
};
Edge graph[MAXN];
struct Tree{
    int next,to,dis;
};
Tree Graph[MAXN];
int head[MAXN],cnt,depth[MAXN];
int doubly[MAXN][MAXB],weight[MAXN][MAXB];
int UFS[MAXN];
bool visited[MAXN];
/* functions */
inline void Add_Edge(int from,int to,int cost){
    Graph[++cnt].next = head[from];
    Graph[cnt].to = to;
    Graph[cnt].dis = cost;
    head[from] = cnt;
}
inline void Ori_Add_Edge(int from,int to,int cost,int place){
    graph[place].from = from;
    graph[place].to = to;
    graph[place].val = cost;
}
inline bool cmp(Edge x,Edge y){
    return x.val > y.val; 
}
inline int Find(int x){
    if(UFS[x] == x)return x;
    return UFS[x]=Find(UFS[x]);
}
inline void unionx(int x,int y,int cost){
    int findx = Find(x);
    int findy = Find(y);
    if(findx != findy){
        UFS[findx] = findy;
        Add_Edge(x,y,cost);
        Add_Edge(y,x,cost);
    }
}
inline void kruskal(){
    std::sort(graph+1,graph+m+1,cmp);
    FOR(i,1,n,1)UFS[i] = i;
    FOR(i,1,m,1)unionx(graph[i].from,graph[i].to,graph[i].val);
    return;
}
inline void DFS(int now){
    visited[now] = true;
    for(int i=head[now];i;i=Graph[i].next){
        if(visited[Graph[i].to])continue;
        depth[Graph[i].to] = depth[now] + 1;
        doubly[Graph[i].to][0] = now;
        weight[Graph[i].to][0] = Graph[i].dis;
        DFS(Graph[i].to);
    }
}
inline void LCAinit(){
    FOR(i,1,20,1){
        FOR(j,1,n,1){
            doubly[j][i] = doubly[doubly[j][i-1]][i-1];
            weight[j][i] = std::min(weight[j][i-1],weight[doubly[j][i-1]][i-1]);
        }
    }
}
inline int LCA(int x,int y){
    if(Find(x) != Find(y))return -1;
    int ans = INT_MAX;
    if(depth[x] > depth[y])std::swap(x,y);
    ROF(i,20,0,1){
        if(depth[doubly[y][i]] >= depth[x]){
            ans = std::min(ans,weight[y][i]);
            y = doubly[y][i];
        }
    }
    if(x == y)return ans;
    ROF(i,20,0,1){
        if(doubly[x][i] != doubly[y][i]){
            ans = std::min(ans,std::min(weight[x][i],weight[y][i]));
            x = doubly[x][i];
            y = doubly[y][i];
        }
    }
    ans = std::min(ans,std::min(weight[x][0],weight[y][0]));
    return ans;
}
int main(int argc,char *argv[]){
    scanf("%d%d",&n,&m);
    FOR(i,1,m,1){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        Ori_Add_Edge(x,y,z,i);
    }
    kruskal();
    FOR(i,1,n,1){
        if(!visited[i]){
            depth[i] = 1; DFS(i); doubly[i][0] = i; weight[i][0] = INT_MAX;
        }
    }
    LCAinit();
    int q;
    scanf("%d",&q);
    FOR(i,1,q,1){
        int l,r;
        scanf("%d%d",&l,&r);
        int ans = LCA(l,r);
        print(ans);
    }
    return 0;
}

洛谷P1967「NOIP2013提高组」题解