Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Once again, James Bond is on his way to saving the world. Bond's latest mission requires him to travel between several pairs of cities in a certain country.

The country has N cities (numbered by 1, 2, . . ., N), connected by M bidirectional roads. Bond is going to steal a vehicle, and drive along the roads from city s to city t. The country's police will be patrolling the roads, looking for Bond, however, not all roads get the same degree of attention from the police.

More formally, for each road MI6 has estimated its dangerousness, the higher it is, the more likely Bond is going to be caught while driving on this road. Dangerousness of a path from s to t is defined as the maximum dangerousness of any road on this path.

Now, it's your job to help Bond succeed in saving the world by finding the least dangerous paths for his mission.

Input

There will be at most 5 cases in the input file.

The first line of each case contains two integers N, M (2 ≤ N≤ 50000, 1≤ M ≤ 100000) – number of cities and roads. The next M lines describe the roads. The i-th of these lines contains three integers: x_i, y_i, d_i (1 ≤ x_i, y_i ≤ N, 0 ≤ d_i ≤ 10⁹) - the numbers of the cities connected by the ith road and its dangerousness.

Description of the roads is followed by a line containing an integer Q (1 ≤ Q ≤ 50000), followed by Q lines, the i-th of which contains two integers s_i and t_i (1 ≤ s_i, t_i  ≤ N, s_i != t_i).

Consecutive input sets are separated by a blank line.

Output

For each case, output Q lines, the i-th of which contains the minimum dangerousness of a path between cities s_i and t_i. Consecutive output blocks are separated by a blank line.

The input file will be such that there will always be at least one valid path.

ProblemSetter: Ivan Krasilnikov

題目描述：

邦德(Bond) 要從某一個城市移動到另一個城市，每個路徑上都有危險度，為了怕被警察抓到，
邦德盡可能走危險度最低的路徑，也就是說他會走一條路徑上最大危險度中最小的那一條。

題目有多組詢問，輸出最小最大危險度路徑的值。

題目解法：

很明顯地，盡可能使用危險度低的建造一張圖，而所有簡單路徑在上面運行。
因此，我們需要使用最小生成樹，如此一來可以保證所有路徑只會發生在這棵樹上。

現在問題變成，找樹上的最大瓶頸路，先將樹轉換成有根樹。
思考一下 LCA 的問題(最鄰近共同祖先)，雖然問題差不多，但是為了求出最大瓶頸路到共同祖先，
我們考慮使用倍增算法，從這個節點開始，往上爬 1 層 2 層 4 層 8 層 ... 的最大瓶頸路，
這裡的遞迴條件是很簡單的。

對於如何查找就稍微困難些，首先，我們將每一個節點按照深度分層，對於查找 (x, y)，
事先將調整到相同層，再根據 greedy 的方式，將他們推到共同祖先。

建表 O (n log n)，每次查詢 O(log n)

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
struct E {
    int x, y, v;
    E(int a=0, int b=0, int c=0):
        x(a), y(b), v(c) {}
    bool operator<(const E &a) const {
        return v < a.v;
    }
};
struct Edge {
    int to, v;
    Edge(int a=0, int b=0):
        to(a), v(b)  {}
};
E D[100005];
vector<Edge> g[50005];
int parent[50005], rank[50005];
int getParent(int x) {
    return parent[x] == x ? x : parent[x]=getParent(parent[x]);
}
int joint(int x, int y) {
    x = getParent(x), y = getParent(y);
    if(x == y)    return 0;
    if(rank[x] > rank[y])
        rank[x] += rank[y], parent[y] = x;
    else
        rank[y] += rank[x], parent[x] = y;
    return 1;
}
void MST(int n, int m) {//Kruskal algorithm
    sort(D, D+m);
    int i;
    for(i = 1; i <= n; i++) {
        g[i].clear();
        parent[i] = i, rank[i] = 1;
    }
    for(i = 0; i < m; i++) {
        if(joint(D[i].x, D[i].y)) {
            g[D[i].x].push_back(Edge(D[i].y, D[i].v));
            g[D[i].y].push_back(Edge(D[i].x, D[i].v));
        }
    }
}
int depth[50005], visited[50005];
int dp[50005][18], dpRoot[50005][18];// Doubling algorithm
void dfs(int nd, int p, int w) {
    visited[nd] = 1;
    depth[nd] = depth[p]+1;
    dpRoot[nd][0] = p;
    dp[nd][0] = w;
    int i, j;
    Edge e;
    for(i = 1, j = 2; j <= depth[nd]; i++, j <<= 1) {
        dp[nd][i] = max(dp[nd][i-1], dp[dpRoot[nd][i-1]][i-1]);
        dpRoot[nd][i] = dpRoot[dpRoot[nd][i-1]][i-1];
    }
    for(i = g[nd].size()-1; i >= 0; i--) {
        e = g[nd][i];
        if(e.to == p)    continue;
        dfs(e.to, nd, e.v);
    }
}
int query(int x, int y) {
    int ret = -0xfffffff;
    int i, j;
    if(depth[x] < depth[y])
        swap(x, y);
    if(depth[x] > depth[y]) {// adjust same level.
        int diff = depth[x] - depth[y];
        for(i = 0; diff; i++) {
            if((diff>>i)&1) {
                ret = max(ret, dp[x][i]);
                x = dpRoot[x][i];
                diff ^= 1<<i;
            }
        }
    }
    if(x != y) {
        for(i = 16; i >= 0; i--) {
            if(dpRoot[x][i] != dpRoot[y][i]) {
                ret = max(ret, dp[x][i]);
                ret = max(ret, dp[y][i]);
                x = dpRoot[x][i];
                y = dpRoot[y][i];
            }
        }
        ret = max(ret, dp[x][0]);
        ret = max(ret, dp[y][0]);
    }
    return ret;
}
int main() {
    int n, m, q;
    int i, j, x, y;
    int cases = 0;
    while(scanf("%d %d", &n, &m) == 2) {
        if(cases++)   
            puts("");
        for(i = 0; i < m; i++)
            scanf("%d %d %d", &D[i].x, &D[i].y, &D[i].v);
        MST(n, m);
        memset(visited, 0, sizeof(visited));
        memset(dp, 0, sizeof(dp));
        memset(dpRoot, 0, sizeof(dpRoot));
        depth[0] = 0;//init
        for(i = 1; i <= n; i++) {
            if(visited[i] == 0) {
                dfs(i, 0, 0);
            }
        }
        scanf("%d", &q);
        while(q--) {
            scanf("%d %d", &x, &y);
            printf("%d\n", query(x, y));
        }
    }
    return 0;
}
/*
4 5
1 2 10
1 3 20
1 4 100
2 4 30
3 4 10
2
1 4
4 1
 
2 1
1 2 100
1
1 2
*/