UVA 11354 Bond（MST + LCA）

n<=50000, m<=100000的無向圖，對於Q<=50000個詢問，每次求q->p的瓶頸路。

其實求瓶頸路數組maxcost[u][v]有用鄰接矩陣prim的方法。但是對於這個題的n，鄰接矩陣是存不下的。。。所以默默的抄了一遍大白書上的算法。。。先用kruskal求MST，然後對於MST樹，每次詢問求p和q的LCA,在求LCA的過程中順便求出瓶頸路。。。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<fstream>
#include<sstream>
#include<bitset>
#include<vector>
#include<string>
#include<cstdio>
#include<cmath>
#include<stack>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define FF(i, a, b) for(int i=a; i<b; i++)
#define FD(i, a, b) for(int i=a; i>=b; i--)
#define REP(i, n) for(int i=0; i<n; i++)
#define CLR(a, b) memset(a, b, sizeof(a))
#define debug puts("**debug**")
#define LL long long
#define PB push_back
using namespace std;

const int maxn = 50005;
const int maxm = 100010;
const int INF = 1e9;
int n, m;
int fa[maxn], pa[maxn], cost[maxn], L[maxn], anc[maxn][100], maxcost[maxn][100];
struct Edge
{
    int to, dist;
};
vector<Edge> edges;
vector<int> G[maxn];
inline void add(int a, int b, int c)
{
    edges.PB((Edge){b, c});
    edges.PB((Edge){a, c});
    int nc = edges.size();
    G[a].PB(nc-2); G[b].PB(nc-1);
}

inline void init()
{
    L[1] = cost[1] = 0;
    REP(i, n+1) pa[i] = i;
    REP(i, n+1) G[i].clear(); edges.clear();
}

int findset(int x) {    return x == pa[x] ? x : pa[x] = findset(pa[x]); }

struct E
{
    int u, v, w;
    bool operator < (const E rhs) const
    {
        return w < rhs.w;
    }
}e[maxm];

void MST()
{
    sort(e, e+m);
    int cnt = 0;
    REP(i, m)
    {
        int x = findset(e[i].u), y = findset(e[i].v);
        if(x != y)
        {
            pa[x] = y;
            cnt++;
            add(e[i].u, e[i].v, e[i].w);
        }
        if(cnt == n-1) return ;
    }
}

void dfs(int u, int f)
{
    fa[u] = f;
    int nc = G[u].size();
    REP(i, nc)
    {
        int v = edges[G[u][i]].to, w = edges[G[u][i]].dist;
        if(v != f)
        {
            cost[v] = w;
            L[v] = L[u] + 1;
            dfs(v, u);
        }
    }
}

void progress()
{
    FF(i, 1, n+1)
    {
        anc[i][0] = fa[i], maxcost[i][0] = cost[i];
        for(int j=1; (1 << j) < n; j++) anc[i][j] = -1;
    }
    for(int j=1; (1 << j) < n; j++) FF(i, 1, n+1)
    if(anc[i][j-1] != -1)
    {
        int a = anc[i][j-1];
        anc[i][j] = anc[a][j-1];
        maxcost[i][j] = max(maxcost[i][j-1], maxcost[a][j-1]);
    }
}

int query(int p, int q)
{
    int lo;
    if(L[p] < L[q]) swap(p, q);
    for(lo = 1; (1 << lo) <= L[p]; lo++); lo--;

    int ans = -INF;
    FD(i, lo, 0)
        if(L[p] - (1<<i) >= L[q]) ans = max(ans, maxcost[p][i]), p = anc[p][i];

    if(p == q) return ans; //LCA -> p

    FD(i, lo, 0)
    if(anc[p][i] != -1 && anc[p][i] != anc[q][i])
    {
        ans = max(ans, maxcost[p][i]), p = anc[p][i];
        ans = max(ans, maxcost[q][i]), q = anc[q][i];
    }

    ans = max(ans, cost[p]);
    ans = max(ans, cost[q]);
    return ans; //LCA -> fa[q] fa[p]
}

int main()
{
    int flag = 0;
    while(~scanf("%d%d", &n, &m))
    {
        if(flag++) puts("");

        init();
        REP(i, m) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);

        MST();
        dfs(1, -1);
        progress();

        int Q, p, q;
        scanf("%d", &Q);
        while(Q--)
        {
            scanf("%d%d", &p, &q);
            printf("%d\n", query(p, q));
        }
    }
    return 0;
}