题目描述
A 国有 nn 座城市，编号从 11 到 nn，城市之间有 mm 条双向道路。每一条道路对车辆都有重量限制，简称限重。
现在有 qq 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入格式
第一行有两个用一个空格隔开的整数 n,mn,m，表示 AA 国有 nn 座城市和 mm 条道路。
接下来 mm 行每行三个整数 x, y, zx,y,z，每两个整数之间用一个空格隔开，表示从 xx 号城市到 yy 号城市有一条限重为 zz 的道路。
注意： x \neq yx=y，两座城市之间可能有多条道路 。
接下来一行有一个整数 qq，表示有 qq 辆货车需要运货。
接下来 qq 行，每行两个整数 x,yx,y，之间用一个空格隔开，表示一辆货车需要从 xx 城市运输货物到 yy 城市，保证 x \neq yx=y
输出格式
共有 qq 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。
如果货车不能到达目的地，输出 -1−1。
输入输出样例
输入 #1复制
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
输出 #1复制
3
-1
3
思路
这题Floyd肯定是不能做的，考虑其他办法。
类似于静态树上求节点之间的最小边权可做。
显然这颗静态树的边权要尽可能的大，且注意到很多较小的重边是不用去跑的，所以考虑只把最大的边加入连通块，舍弃小的重边。
对于两座城市，如果不在同一个连通块内，当然是不能跑的，输出-1；
如果在同一个连通块内，因为边点和询问的数量级过大，显然正常的枚举是不足以胜任此题要求的。
这就涉及到静态树上求节点之间的最小边权问题。
对于这种问题，可以上树链剖分用线段树来维护，也可以用树上问题的经典解法LCA来求解。
在处理 f 数组的过程中维护一个 dis 数组用以表示点间最小边权值即可。
CODE
#include <bits/stdc++.h>
#define dbg(x) cout << #x << "=" << x << endl
#define eps 1e-8
#define pi acos(-1.0) using namespace std;
typedef long long LL; template<class T>inline void read(T &res)
{
char c;T flag=;
while((c=getchar())<''||c>'')if(c=='-')flag=-;res=c-'';
while((c=getchar())>=''&&c<='')res=res*+c-'';res*=flag;
} namespace _buff {
const size_t BUFF = << ;
char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
char getc() {
if (ib == ie) {
ib = ibuf;
ie = ibuf + fread(ibuf, , BUFF, stdin);
}
return ib == ie ? - : *ib++;
}
} int qread() {
using namespace _buff;
int ret = ;
bool pos = true;
char c = getc();
for (; (c < '' || c > '') && c != '-'; c = getc()) {
assert(~c);
}
if (c == '-') {
pos = false;
c = getc();
}
for (; c >= '' && c <= ''; c = getc()) {
ret = (ret << ) + (ret << ) + (c ^ );
}
return pos ? ret : -ret;
} const int maxn = 1e5 + ; int n, m, cnt;
int head[maxn << ], edge[maxn << ], nxt[maxn << ];
int fa[maxn], f[maxn][], depth[maxn], w[maxn << ];
int dis[maxn][]; bool vis[maxn]; struct node {
int u, v, w;
} e[maxn << ]; bool cmp(node a, node b) {
return a.w > b.w;
} void BuildGraph(int u, int v, int c) {
cnt++;
edge[cnt] = v;
nxt[cnt] = head[u];
w[cnt] = c;
head[u] = cnt;
} int fid(int x) {
return x == fa[x] ? x : fid(fa[x]);
} void join() {
sort(e+, e+m+, cmp);
for ( int i = ; i <= n; ++i ) {
fa[i] = i;
}
for ( int i = ; i <= m; ++i ) {
int eu = fid(e[i].u), ev = fid(e[i].v);
if(eu != ev) {
fa[eu] = ev;
BuildGraph(e[i].u, e[i].v, e[i].w);
BuildGraph(e[i].v, e[i].u, e[i].w);
//dbg(e[i].w);
}
}
} void dfs(int x) {//找x和y的最近公共祖先
vis[x] = ;
for ( int i = head[x]; i; i = nxt[i] ) {
int y = edge[i];
if(!vis[y]) {
depth[y] = depth[x] + ;
f[y][] = x;//y向上跳肯定是x
dis[y][] = w[i];
dfs(y);
}
}
} int lca(int x, int y) {//查找xy的最近公共祖先
int ans = 0x3f3f3f3f;
if(fid(x) != fid(y)) {
return -;
}
if(depth[x] < depth[y])
swap(x, y);//保证x是比y深的
for ( int i = ; i >= ; --i ) {
if(depth[f[x][i]] >= depth[y]) {//让x跳到和y同一层
ans = min(ans, dis[x][i]);
x = f[x][i];
}
}
if(x == y) {///重合态
return ans;
}
for ( int i = ; i >= ; --i ) {///不重合一起跳
if(f[x][i] != f[y][i]) {//父亲不同要跳一步
ans = min(ans, min(dis[y][i], dis[x][i]));
x = f[x][i], y = f[y][i];
}
}
ans = min(ans, min(dis[x][], dis[y][]));
return ans;///跳完最后一步
} int main()
{
scanf("%d %d", &n, &m);
for ( int i = ; i <= m; ++i ) {
scanf("%d %d %d",&e[i].u, &e[i].v, &e[i].w);
}
join();
for ( int i = ; i <= n; ++i ) {
if(!vis[i]) {
depth[i] = ;
dfs(i);
f[i][] = i;
dis[i][] = 0x3f3f3f3f;
}
}
for ( int i = ; i <= ; ++i ) {
for ( int j = ; j <= n; ++j ) {
f[j][i] = f[f[j][i - ]][i - ];
dis[j][i] = min(dis[j][i - ], dis[f[j][i - ]][i - ]);
//printf("dis[%d][%d]:%d\n",j,i-1,dis[j][i-1]);
//printf("dis[%d][%d]:%d\n\n",fa[j][i-1],i-1,dis[fa[j][i-1]][i-1]);
}
}
int q;
cin >> q;
for ( int i = ; i <= q; ++i ) {
int x, y;
scanf("%d %d", &x, & y);
printf("%d\n",lca(x,y));
}
return ;
}