有的时候需要转换给定的图(比如转成树)

懵逼的 题目

传送至 Codevs
大意:给定一个无向图 求两点之间的最大的最小值
(然而这题gty学长在夏令营讲过我还崩了三天…还不如初中没学oi的dalao们QAQ宽嫂怕不是坏掉了QAQ)

扯淡的 题解

数据范围太大…SPFA只有60…因为是求最大的最小值…又不能同时走两条路(否则估计就是网络流板子了?) 所以如果两点之间有两条路 我们就可以只保留大的…这样就把图转化为了一棵最大生成树…就可以跑nlogn的LCA了…
又及:LCA写挂了两天…一个是初始化数组名字混了(5分没了)…(趴) 一个是倍增跳到同一深度时没有检查是否已经是一个点了(90分没了)…(趴…惨痛教训…)

沙茶的 代码

//http://codevs.cn/problem/3287/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MAXN (10000 + 5)
#define MAXM (50000 + 5)
#define MAXL (15 + 5)
#define INF (0x7ffffff)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define swap(a, b) {int t = a; a = b; b = t;}
using namespace std;
vector<int> root;
struct edgg
{
    int from;
    int to;
    int cost;
}a[MAXM];// kruskal's edge
struct edgt
{
    int to;
    int cost;
    int next;
}b[MAXN * 2];// tree's edge
int cntm = 0;// add a edge
int cntc = 0;// add a kind of color
int lgn;
int n;// number of nodes
int m;// number of edges
int g[MAXN];// vector 
int f[MAXN];// bcj
int fa[MAXN];// fa[i] means i's father is f[i]
int d[MAXN][MAXL];// lca
int deep[MAXN];// deep in its tree
int minc[MAXN][MAXL];// the min cost in the road
int col[MAXN];// a node's color 
int lg(int);
bool cmp(edgg, edgg);
void adn(int, int, int);// add a edge
int find(int);
void uni(int, int);
void kruskal();
void dfs(int, int);// inint
int lca(int, int);
int main()
{
    memset(col, 0, sizeof(col));
    scanf("%d%d", &n, &m);
    lgn = lg(n);
    int srx, sry, srz;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &a[i].from, &a[i].to, &a[i].cost);
    }
    kruskal();
    for (int i = 1; i <= n; i++)
    {
        if (!col[i])
        {
            root.push_back(i);
            fa[i] =    d[i][0] = i;
            minc[i][0] = INF;
            col[i] = ++cntc;
            dfs(i, 1);
        }
    }
    /*for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= lgn; j++)
        {
            printf("%d ",minc[i][j]);
        }
        puts("");
    }*/
    int q;
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)
    {
        scanf("%d%d", &srx, &sry);
        if (col[srx] != col[sry])
        {
            puts("-1");
        }
        else
        {
            printf("%d\n", lca(srx, sry));
        }
    }
    return 0;
}
void adn(int f, int t, int c)
{
    b[++cntm].next = g[f];
    b[cntm].to = t;
    b[cntm].cost = c;
    g[f] = cntm;
}
int lg(int x)
{
    int re = 0;
    int i = 0;
    for(;re <= x; i++)
    {
        re = (1 << i);
    }
    return i;
}
bool cmp(edgg x, edgg y)
{
    return x.cost > y.cost;
}
int find(int x)
{
    return x == f[x] ? x : (f[x] = find(f[x]));
}
void uni(int x, int y)
{
    int fx = find(x);
    int fy = find(y);
    f[fx] = fy;
}
void kruskal()
{
    for (int i = 1; i <= n; i++)
    {
        f[i] = i;
    }
    sort(a + 1, a + m + 1, cmp);
    int cntb = 0;
    for (int i = 1; i <= m; i++)
    {
        if (cntb == n - 1)
        {
            break;
        }
        int fx = find(a[i].from);    int fy = find(a[i].to);
        if (fx != fy)
        {
            adn(a[i].from, a[i].to, a[i].cost);
            adn(a[i].to, a[i].from, a[i].cost);
            uni(fx, fy);
            ++cntb;
        }
    }
}
void dfs(int dq, int de)
{
    col[dq] = cntc;
    deep[dq] = de;
    for (int i =  1; i <= lgn; i++)
    {
        d[dq][i] = d[d[dq][i - 1]][i - 1];
        minc[dq][i] = min(minc[dq][i - 1], minc[d[dq][i - 1]][i - 1]);
    }
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (b[i].to != fa[dq])
        {
            d[b[i].to][0] = fa[b[i].to] = dq;
            minc[b[i].to][0] = b[i].cost;
            dfs(b[i].to, de + 1);
        }
    }
}
int lca(int x, int y)
{
    if (deep[x] < deep[y])
    {
        swap(x, y);
    }
    int re = INF;
    for (int i = lgn; i >= 0; i--)
    {
        if (deep[x] == deep[y])
        {
            break;
        }
        if (deep[d[x][i]] >= deep[y])
        {
            re = min(re, minc[x][i]);
            x = d[x][i];
        }
    }
    if (x == y)
    return re;
    for (int i = lgn; i >= 0; i--)
    {
        if (d[x][i] != d[y][i])
        {
            re = min(re, min(minc[x][i], minc[y][i]));
            x = d[x][i];
            y = d[y][i];
        }
    }
    return min(re, min(minc[x][0], minc[y][0]));
}
/*
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
*/

By win10被可怕学弟搞崩还逃不了军训的可怜 Cansult