gym 101889I Imperial roads 最小生成树+LCA

题意：

给出一幅无向带权图，q次询问，每次询问都求一棵包含给出的边的最小生成树。

思路：

首先求出最小生成树（kruskal），如果查询的边在最小生成树上，肯定是直接输出最小生成树，如果不在树上，那么这条必须连的边会和生成树形成一个环，我们就要去掉这个环上最大的一条边，就得到了答案（最小生成树是通过局部最优解得到全局最优解的，所以如果这样做，得到的是符合要求的最优解）。

赛中队友提出一个问题，如果有两棵不同的最小生成树那这个做法不就错了吗，但其实如果有两棵最小生成树，这两棵树相同权值的边的条数是一样的，是同分异构，所以做法还是正确的。

而求环上的最大值，其实是求树上的最大值，所以在做kruskal的时候建立一幅新图，然后用lca求最大值。注意最大值的更新，很容易错。

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<vector>

#include<map>

#include<set>

#include<cstring>

#include<queue>

#include<stack>

#include<cmath>

#define CLR(a,b) memset(a,b,sizeof(a))

#define mkp(a,b) make_pair(a,b)

using namespace std;

const int maxn = ;

typedef long long ll;

int n, m, head[maxn], tot, vis[maxn],fa[maxn],deep[maxn],t,f[maxn][],ma[maxn][];

int ans;

struct edge {

    int to, w, Next;

    edge() {}

    edge(int to, int Next, int w) :to(to), Next(Next), w(w) {}

}a[maxn * ];

map<pair<int, int >, int >mp;

struct node {

    int u, v, w;

    node(int u, int v, int w) :u(u), v(v), w(w) {}

};

vector<node>g;

void addv(int u, int v, int w) {

    a[++tot] = { v,head[u],w };

    head[u] = tot;

}

void init() {

    CLR(head, -);

    for (int i = ; i <= n; i++)fa[i] = i;

    tot = ;

}

int find(int x)

{

    return x == fa[x] ? x : fa[x] = find(fa[x]);

}

inline void baba(int x, int y)

{

    int fx = find(x), fy = find(y);

    fa[fx] = fy;

}

bool cmp(node &a, node &b)

{

    return a.w < b.w;

}

inline void kruskal() {

    sort(g.begin(), g.end(), cmp);

    for (int i = ; i < m; i++)

    {

        int x = find(g[i].u);

        int y = find(g[i].v);

        if (x == y)continue;

        addv(g[i].u, g[i].v, g[i].w);

        addv(g[i].v, g[i].u, g[i].w);

        baba(x, y);

        ans += g[i].w;

    }

}

inline void bfs() {

    queue<int >q;

    q.push();

    deep[] = ;

    while (!q.empty())

    {

        int x = q.front();

        q.pop();

        for (int i = head[x]; i != -; i = a[i].Next)

        {

            int y = a[i].to;

            if (deep[y])continue;

            deep[y] = deep[x] + ;

            f[y][] = x;

            ma[y][] = a[i].w;

            for (int j = ; j <= t; j++)

            {

                f[y][j] = f[f[y][j - ]][j - ];

                ma[y][j] = max(ma[y][j-], ma[f[y][j - ]][j - ]);

            }

            q.push(y);

        }

    }

}

int lca(int x, int y)

{

    int maxx = ;

    if (deep[x] > deep[y])swap(x, y);

    for (int i = t; i >= ; i--)

    {

        if (deep[f[y][i]] >= deep[x]) {

            maxx = max(maxx, ma[y][i]);

            y = f[y][i];

        }

    }

    if (x == y)return maxx;

    for (int i = t; i >= ; i--)

    {

        if (f[x][i] != f[y][i]) {

            maxx = max(maxx, ma[x][i]);

            maxx = max(maxx, ma[y][i]);

            x = f[x][i], y = f[y][i];

        }

    }

    //printf("debug\n");

    maxx=max(maxx,ma[x][]);

    maxx=max(maxx,ma[y][]);

    return maxx;

}

int main() {

    scanf("%d%d", &n, &m);

    init();

    for(int i=;i<=m;i++)

    {

        int u, v;

        int w;

        scanf("%d%d%d", &u, &v, &w);

        if (u > v)swap(u, v);

        mp[make_pair(u, v)] = w;

        g.push_back(node{ u,v,w });

    }

    kruskal();

    t = (int)(log(n) / log()) + ;

    bfs();

//    for (int i = 1; i <= n; i++)

//    {

//        printf("i:%d  deep:%d\n", i, deep[i]);

//    }

    int q;

    cin >> q;

    while (q--)

    {

        int u, v;

        scanf("%d%d", &u, &v);

        if (u > v)swap(u, v);

    //    printf("u:%d  v:%d\n", u, v);

    //    printf("ans:%d   lca:%d  mp:%d\n",ans,lca(u,v),mp[make_pair(u,v)]);

        printf("%d\n", ans - lca(u, v)+mp[make_pair(u,v)]);

    }

}

/*

5 7

1 2 6

1 3 4

3 4 2

1 5 7

4 5 4

2 4 1

3 5 3

1

4 5

*/