《P1967 [NOIP 2013 提高组] 货车运输》
题目背景
NOIP2013 提高组 D1T3
题目描述
A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。
现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入格式
第一行有两个用一个空格隔开的整数 n,m，表示 A 国有 n 座城市和 m 条道路。
接下来 m 行每行三个整数 x,y,z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。
注意：x=y，两座城市之间可能有多条道路。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x,y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，保证 x=y。
输出格式
共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。
如果货车不能到达目的地，输出 −1。
输入输出样例
输入 #1复制
4 3 1 2 4 2 3 3 3 1 1 3 1 3 1 4 1 3
输出 #1复制
3 -1 3
说明/提示
对于 30% 的数据，1≤n<1000，1≤m<10,000，1≤q<1000；
对于 60% 的数据，1≤n<1000，1≤m<5×104，1≤q<1000；
对于 100% 的数据，1≤n<104，1≤m<5×104，1≤q<3×104，0≤z≤105。
代码实现：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#define N 10003
#define inf 0x3f3f3f3f
using namespace std;
struct Edge{
int from, to, weight;
Edge(int f=0,int t=0,int w=0):from(f),to(t),weight(w){}
bool operator < (const Edge& a) const{
return weight > a.weight;
}
};
int up[N][15], depth[N], lg2[N];
int father[N], minWeight[N][15];
bool visited[N];
vector<Edge> adj[N];
Edge edges[50003];
int nodeCount, edgeCount;
inline int min(int a,int b){
if(a > b) return b;
return a;
}
int find(int node){
if(father[node] == node) return node;
father[node] = find(father[node]);
return father[node];
}
inline void read(int &x){
x = 0;
char c = getchar();
while(!isdigit(c)) c = getchar();
while(isdigit(c)){
x = (x<<3)+(x<<1)+c-'0';
c = getchar();
}
}
inline int getWeight(int current, int neighbor){
int length = adj[current].size();
for(int i=0; i<length; ++i){
if(neighbor == adj[current][i].to)
return adj[current][i].weight;
}
}
void dfs(int current, int parent){
visited[current] = true;
depth[current] = depth[parent] + 1;
up[current][0] = parent;
int w, grandparent, neighbor, length, t = lg2[depth[current]];
w = getWeight(current, parent);
minWeight[current][0] = w;
if(parent == 0) minWeight[current][0] = inf;
for(int i=1; i<t; ++i){
grandparent = up[current][i-1];
minWeight[current][i] = min(minWeight[current][i-1], minWeight[grandparent][i-1]);
up[current][i] = up[grandparent][i-1];
}
length = adj[current].size();
for(int i=0; i<length; ++i){
neighbor = adj[current][i].to;
if(neighbor == parent) continue;
dfs(neighbor, current);
}
}
int lca(int u, int v){
if(find(u) ^ find(v)) return -1;
int temp, res = inf;
if(depth[u] < depth[v]){
temp = u;
u = v;
v = temp;
}
while(depth[u] > depth[v]){
temp = lg2[depth[u]-depth[v]] - 1;
res = min(res, minWeight[u][temp]);
u = up[u][temp];
}
if(u == v) return res;
for(temp = lg2[depth[u]] - 1; temp >= 0; --temp){
if(up[u][temp] == up[v][temp]) continue;
res = min(res, min(minWeight[u][temp], minWeight[v][temp]));
u = up[u][temp];
v = up[v][temp];
}
res = min(res, min(minWeight[u][0], minWeight[v][0]));
return res;
}
void kruskal(){
sort(edges + 1, edges + 1 + edgeCount);
int remain = nodeCount - 1;
for(int i=1; i<=edgeCount; ++i){
if(remain == 0) break;
int rootU, rootV, fromNode, toNode, weight;
fromNode = edges[i].from;
toNode = edges[i].to;
weight = edges[i].weight;
rootU = find(fromNode);
rootV = find(toNode);
if(rootU == rootV) continue;
father[rootU] = rootV;
--remain;
adj[fromNode].push_back(Edge(fromNode, toNode, weight));
adj[toNode].push_back(Edge(toNode, fromNode, weight));
}
}
int main(){
memset(minWeight, inf, sizeof(minWeight));
int u, v, w, queryCount;
read(nodeCount), read(edgeCount);
for(int i=1; i<=nodeCount; ++i) father[i] = i;
for(int i=1; i<=edgeCount; ++i){
read(u), read(v), read(w);
edges[i] = Edge(u, v, w);
}
kruskal();
lg2[1] = 1;
for(int i=2; i<=nodeCount; ++i)
lg2[i] = lg2[i-1] + (i >> lg2[i-1] == 1);
for(int i=1; i<=nodeCount; ++i){
if(visited[i]) continue;
dfs(i, 0);
}
read(queryCount);
++queryCount;
while(--queryCount){
read(u), read(v);
printf("%d\n", lca(u, v));
}
return 0;
}