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
", query(p, q));

        }

    }

    return 0;

}