题目描述
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;
}
Comments NOTHING