点我传送

题目描述

AA国有nn座城市，编号从 11到nn，城市之间有 mm 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 qq 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入格式

第一行有两个用一个空格隔开的整数n,mn,m，表示 AA 国有nn 座城市和 mm 条道路。

接下来 mm行每行33个整数 x, y, zx,y,z，每两个整数之间用一个空格隔开，表示从 xx号城市到yy号城市有一条限重为 zz 的道路。注意： xx 不等于 yy，两座城市之间可能有多条道路 。

接下来一行有一个整数 q，表示有 q 辆货车需要运货。

接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： x 不等于 y 。

输出格式

共有 qq 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1−1。

输入输出样例

输入

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

输出

3
-1
3

说明/提示

对于 30\%30%的数据，0 < n < 1,000,0 < m < 10,000,0 < q< 1,0000<n<1,000,0<m<10,000,0<q<1,000；

对于 60\%60%的数据，0 < n < 1,000,0 < m < 50,000,0 < q< 1,0000<n<1,000,0<m<50,000,0<q<1,000；

对于 100\%100%的数据，0 < n < 10,000,0 < m < 50,000,0 < q< 30,000,0 ≤ z ≤ 100,0000<n<10,000,0<m<50,000,0<q<30,000,0≤z≤100,000。

题解

这题解法很显然

我们跑一边最大生成树，然后求LCA。

有没有发现LCA不好维护最大载重，那我们用克鲁斯卡尔重构树即可。

先把边权从大到小排个序，然后建立一个克鲁斯卡尔重构树，对于每个询问，直接LCA便可，起点到终点在树上的LCA的点权即为答案。

CODE (我十分毒瘤的用了树剖求LCA)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <cmath>
#include <vector>
#define endl '\n'
#define maxn 200010

using namespace std;

struct node
{
    int from, to, data;
    bool operator<(const node &b) const
    {
        return data > b.data;
    }
} edge[maxn << 2];

struct node2
{
    int to, next;
} e[maxn << 2];

int head[maxn], num = 0, a[maxn];
int n, m, q, cnt;

int fa[maxn], dep[maxn], top[maxn], _size[maxn], son[maxn], val[maxn], vis[maxn];

inline void add_edge(int from, int to)
{
    e[++num].next = head[from];
    e[num].to = to;
    head[from] = num;
}

int find(int x)
{
    if (a[x] == x)
        return x;
    return a[x] = find(a[x]);
}

void dfs1(int u, int f, int deep)
{
    vis[u] = true;
    fa[u] = f;
    dep[u] = deep;
    _size[u] = 1;
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v == f)
            continue;
        dfs1(v, u, deep + 1);
        _size[u] += _size[v];
        if (_size[v] > _size[son[u]])
            son[u] = v;
    }
}

void dfs2(int u, int t)
{
    top[u] = t;
    if (!son[u])
        return;
    dfs2(son[u], t);

    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v != son[u] && v != fa[u])
            dfs2(v, v);
    }
}

inline int lca(int a, int b)
{
    while (top[a] != top[b])
        if (dep[top[a]] > dep[top[b]])
            a = fa[top[a]];
        else
            b = fa[top[b]];
    return dep[a] < dep[b] ? a : b;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    cnt = n;
    for (register int i = 1; i <= n; i++)
        a[i] = i;

    for (register int i = 1; i <= m; i++)
        cin >> edge[i].from >> edge[i].to >> edge[i].data;

    sort(edge + 1, edge + m + 1);

    for (register int i = 1; i <= m; i++)
    {
        int x = find(edge[i].from), y = find(edge[i].to);
        if (x != y)
        {
            val[++cnt] = edge[i].data;
            a[cnt] = a[x] = a[y] = cnt;
            add_edge(x, cnt);
            add_edge(cnt, x);
            add_edge(y, cnt);
            add_edge(cnt, y);
        }
    }
    for (int i = 1; i <= cnt; i++)
        if (!vis[i])
        {
            int f = find(i);
            dfs1(f, f, 1);
            dfs2(f, f);
        }

    cin >> q;
    while (q--)
    {
        int x, y;
        cin >> x >> y;
        if (find(x) != find(y))
            cout << "-1\n";
        else
            cout << val[lca(x, y)] << endl;
    }

    return 0;
}

END