P1967 货车运输

xiaoxiao2021-02-28  12

题目描述

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 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。如果货车不能到达目的地,输出 -11

输入输出样例

输入样例#1:  复制 4 3 1 2 4 2 3 3 3 1 1 3 1 3 1 4 1 3 输出样例#1:  复制 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,000

0<n<10,000,0<m<50,000,0<q<30,000,0z100,000 

lca倍增(据说是模板题)

#include<bits/stdc++.h> using namespace std; int n , m; const int MAXN = 100000 + 10; int g[MAXN] , u[2 * MAXN] , v[2 * MAXN] , w[2 * MAXN] , First[2 * MAXN] , Next[2 * MAXN]; int fa[MAXN][21] , ff[MAXN][21] , deep[MAXN]; int inf = 0x7fffffff; struct f { int x; int y; int c; }a[MAXN] ; int com(const f &u , const f &v) { return u.c > v.c; } int bin(int x ) { while(x != g[x]) x = g[x] = g[g[x]]; return x; } void kruskal() { int num = 0; for(int i = 1; i <= m ; i ++) { int x = bin(a[i].x); int y = bin(a[i].y); if(x != y) { g[y] = x; num ++; u[num] = a[i].x; v[num] = a[i].y ; w[num] = a[i].c; Next[num] = First[u[num]]; First[u[num]] = num; u[num + n - 1] = a[i].y ; v[num + n - 1] = a[i].x; w[num + n - 1] = w[num]; Next[num + n - 1] = First[u[num + n - 1]];First[u[num + n - 1]] = num + n - 1; if(num == n - 1) break; } } } void dfs(int q) { for(int k = First[q] ; k != -1; k = Next[k]) { int to = v[k]; if(deep[to] == 0) { deep[to] = deep[q] + 1; fa[to][0] = q; ff[to][0] = w[k]; dfs(to); } } } void ycl() { for(int i = 1; i <= n ; i ++) { if(deep[i] == 0) { deep[i] = 1; fa[i][0] = 0; dfs(i); } } dfs(1); for(int i = 1; i <= 20 ; i ++) { for(int j = 1; j <= n ; j ++) { fa[j][i] = fa[fa[j][i-1]][i-1]; ff[j][i] = min(ff[j][i-1],ff[fa[j][i-1]][i-1]); } } } int lca(int x , int y) { int ans = inf; if(deep[x] < deep[y]) { swap(x , y); } for(int i = 20 ; i >= 0 ; i --) { if(deep[fa[x][i]] >= deep[y]) { ans = min (ans , ff[x][i]); x = fa[x][i]; } } if(x == y) return ans; for(int i = 20 ; i >= 0 ; i --) { if(fa[x][i] != fa[y][i]) { ans = min (ans , min(ff[x][i] , ff[y][i])); x = fa[x][i]; y = fa[y][i]; } } ans = min (ans, min (ff[x][0] , ff[y][0])); return ans; } int main() { cin >> n >> m; for(int i = 1; i <= n ; i ++) { g[i] = i; First[i] = -1; } for(int i = 1 ; i <= m ; i ++) { scanf("%d %d %d" , &a[i].x , &a[i].y , &a[i].c); } sort( a + 1, a + m + 1, com); kruskal(); ycl(); int T; cin >> T; while(T --) { int x , y; scanf("%d %d" , &x , &y); if(bin(x) != bin(y)) { printf("-1\n"); } else { printf("%d\n",lca(x,y)); } } return 0; }
转载请注明原文地址: https://www.6miu.com/read-2650090.html

最新回复(0)