[NOIP2013][Luo1967]货车运输 解题报告

解题报告

---

题目传送门（luogu最后一个数据请忽略）

题目大意：给定一个n个点m条边无向图（有重边，无自环），求q对点之间最小边最大的路径
$0<n<10^4 , 0<m<50,000 , 0<q<30,000$

看到题目很容易想到二分+并查集，这样时间复杂度是$O(log_2^{100000} \times mq).$很明显会超时，那怎么办呢？

尝试求原图的最大生成树，我们可以证明：符合条件的路径一定在最大生成树上（下文的生成树指最大生成树）。证明如下：
不妨假设我们要求点u到点v之间的最大的最小边，如果这条最小边不在生成树上，那么生成树上一定有一条比它大的边连接两个联通快，所以，这条最小边一定在生成树上。

所以问题就转化成了求树上两点间路径上的最小值，有大佬就会跳出来说树剖！但是众所周知，树剖难写，我不会QAQ。可以有更简单的方法，比如说树上倍增，时间复杂度（单次查询）仅为$O(log_2^n)$。

简单介绍一下树上倍增。树上倍增就是利用倍增的思想维护树上的信息。举个栗子，树上倍增最基础的数组就是$fa[i][j]$，表示从$i$这个点向上跳$2^j$步能到达的点的编号，我们可以很方便地预处理出$fa[i][j]$：

$$fa[i][j] = fa[ fa[i][j-1] ][j-1]$$

在树上倍增的同时，我们可以维护很多信息，例如和，最值，GCD等等，这道题需要利用边权最小值，所以可以用$Min[i][j]$表示从$i$这个点向上跳$2^j$步经过的边的最小值，我们可以很方便地预处理出$Min[i][j]$：

$$Min[i][j] = min\{Min[i][j-1], Min[ fa[i][j-1] ][j-1]\}$$

维护出了这些信息后，我们就可以很方便地求出树上两点路径上的最小值了，具体来说，就是先求出u到LCA的最小值，再求出v到LCA的最小值，把它们合并即可。

预处理：

for (int j = 1; j <= 14; ++j)
        for (int i = 1; i <= n; ++i){
            fa[i][j] = fa[ fa[i][j-1] ][j-1];
            Min[i][j] = min(Min[i][j-1] , Min[ fa[i][j-1] ][j-1]);
        }

求两点路径上最小值

int Dis(int u, int v){
    //printf("Dis %d %d ", u, v);
    int L = LCA(u,v); int res = 1000000000;
    int lenu = dep[u] - dep[L];
    for (int j = 0; j <= 14; ++j) if (lenu >> j & 1) res = min(res, Min[u][j]), u = fa[u][j];
    int lenv = dep[v] - dep[L];
    for (int j = 0; j <= 14; ++j) if (lenv >> j & 1) res = min(Min[v][j], res), v = fa[v][j];
    //printf("%d\n", res);
    return res;
}

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxm = 50007;
const int maxn = 10007;
int n, m;
struct Edge{
    int u, v, cost;
} a[maxm];
bool cmp(Edge a, Edge b){
    return a.cost > b.cost;
}
//EdgeTable
int edgenum, head[maxn], Next[maxn << 1], vet[maxn << 1], val[maxn << 1];
inline void addedge(int u, int v, int cost){
    ++edgenum;
    vet[edgenum] = v;
    val[edgenum] = cost;
    Next[edgenum] = head[u];
    head[u] = edgenum;
}
//Union-Set
int Fa[maxn];
int Find(int x){return Fa[x] = Fa[x]==x?Fa[x]:Find(Fa[x]);}
inline void Union(int u, int v){
    int F1 = Find(u), F2 = Find(v);
    if (F1 != F2) Fa[F2] = F1;
}
void Union_Set_init(){
    for (int i = 1; i <= n; ++i)
        Fa[i] = i;
}
int fa[maxn][20], Min[maxn][20], dep[maxn];
void DFS(int u, int pre, int d){
    fa[u][0] = pre; dep[u] = d;
    for (int e = head[u]; e; e = Next[e]){
        int v = vet[e], cost = val[e];
        if (v != pre){
            Min[v][0] = cost;
            //printf("v = %d, cost = %d, %d\n",v, cost, Min[v][0]);
            DFS(v, u, d + 1);
        }
    }
}
int LCA(int u, int v){ //倍增求LCA
    if (dep[u] < dep[v]) swap(u, v);
    int len = dep[u] - dep[v];
    for (int j = 0; j <= 14; ++j) if (len >> j & 1) u = fa[u][j];
    for (int j = 14; j >= 0; --j) if (fa[u][j] != fa[v][j]) u = fa[u][j], v = fa[v][j];
    //printf("LCA %d %d %d\n", u, v, u==v?u:fa[u][0]);
    if (u==v) return u; return fa[u][0];
}
int Dis(int u, int v){ //求两点路径上最小值
    //printf("Dis %d %d ", u, v);
    int L = LCA(u,v); int res = 1000000000;
    int lenu = dep[u] - dep[L];
    for (int j = 0; j <= 14; ++j) if (lenu >> j & 1) res = min(res, Min[u][j]), u = fa[u][j];
    int lenv = dep[v] - dep[L];
    for (int j = 0; j <= 14; ++j) if (lenv >> j & 1) res = min(Min[v][j], res), v = fa[v][j];
    //printf("%d\n", res);
    return res;
}
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i){
        scanf("%d%d%d", &a[i].u, &a[i].v, &a[i].cost);
    }
    sort(a + 1, a + 1 + m, cmp);
    Union_Set_init();
    for (int i = 1; i <= m; ++i){
        int tu = a[i].u, tv = a[i].v, cost = a[i].cost;
        if (Find(tu) != Find(tv)){
            Union(tu, tv);
            addedge(tu, tv, cost);
            addedge(tv, tu, cost);
        }
    }
    for (int i = 1; i <= n; ++i)
        dep[i] = 1;
    DFS(1, 0, 1);
    for (int j = 1; j <= 14; ++j)
        for (int i = 1; i <= n; ++i){
            fa[i][j] = fa[ fa[i][j-1] ][j-1];
            Min[i][j] = min(Min[i][j-1] , Min[ fa[i][j-1] ][j-1]);
        }
    int Q; scanf("%d", &Q);
    while (Q--){
        int u, v; scanf("%d%d", &u, &v);
        if (Find(u) == Find(v))printf("%d\n", Dis(u,v));
        else printf("-1\n");
    }
    /*for (int i = 1; i <= n; ++i){
        for (int j = 0; j <= 2; ++j)
            printf("%d ", Min[i][j]);
        printf("\n");
    }*/
    return 0;
}