[NOIP2013提高]货车运输 题解
题目地址:洛谷:【P1967】货车运输 – 洛谷
题目描述
A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。
输入输出格式
输入格式:
输入文件名为 truck.in。
输入文件第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道路。 接下来 m 行每行 3 个整数 x、 y、 z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意: x 不等于 y,两座城市之间可能有多条道路 。
接下来一行有一个整数 q,表示有 q 辆货车需要运货。
接下来 q 行,每行两个整数 x、y,之间用一个空格隔开,表示一辆货车需要从 x 城市运输货物到 y 城市,注意: x 不等于 y 。
输出格式:
输出文件名为 truck.out。
输出共有 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%的数据,0 < n < 1,000,0 < m < 10,000,0 < q< 1,000;
对于 60%的数据,0 < n < 1,000,0 < m < 50,000,0 < q< 1,000;
对于 100%的数据,0 < n < 10,000,0 < m < 50,000,0 < q< 30,000,0 ≤ z ≤ 100,000。
题解
暴力来做可以Floyd处理出两点路径上的最小边权。
我们考虑一个Kruskal算法的流程,如果是在求最大生成树,则按边权降序对边排序并加边,显然可以保证最大生成树上的路径就是最优解。因此我们把询问转换成了树上问题。
这与树链有关,所以其实我们可以选择使用树链剖分,将边权记在边较深的端点处,并线段树维护最小值。这样做的复杂度是O(n \log^2 n)的。
我们还可以用倍增思想,维护一个倍增路径上的最小权值。只需要在通常的倍增LCA算法上加一点小修改即可。这样做的复杂度是O(n \log n),比树剖更优。
代码
// Code by KSkun, 2018/4
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF
: *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(!isdigit(c)) {
if(c == '-') neg = -1;
c = fgc();
}
while(isdigit(c)) {
res = (res << 1) + (res << 3) + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 10005, MAXM = 50005;
int n, m;
struct Edge {
int to, w;
};
std::vector<Edge> gra[MAXN];
struct Edge1 {
int u, v, w;
} edges[MAXM];
inline bool cmp(Edge1 a, Edge1 b) {
return a.w > b.w;
}
int fa[MAXN];
inline int find(int u) {
return fa[u] == u ? u : fa[u] = find(fa[u]);
}
inline void kruskal() {
int cnt = 0;
for(int i = 1; i <= m; i++) {
int f1 = find(edges[i].u), f2 = find(edges[i].v);
if(f1 == f2) continue;
fa[f2] = f1;
gra[edges[i].u].push_back(Edge {edges[i].v, edges[i].w});
gra[edges[i].v].push_back(Edge {edges[i].u, edges[i].w});
cnt++;
if(cnt >= n - 1) break;
}
}
int anc[MAXN][25], mn[MAXN][25], dep[MAXN];
inline void dfs(int u) {
for(auto e : gra[u]) {
int v = e.to;
if(v == anc[u][0]) continue;
anc[v][0] = u;
mn[v][0] = e.w;
dep[v] = dep[u] + 1;
dfs(v);
}
}
inline void calanc() {
for(int i = 1; i <= 20; i++) {
for(int j = 1; j <= n; j++) {
anc[j][i] = anc[anc[j][i - 1]][i - 1];
mn[j][i] = std::min(mn[j][i - 1], mn[anc[j][i - 1]][i - 1]);
}
}
}
inline int query(int x, int y) {
if(dep[x] > dep[y]) std::swap(x, y);
int ans = 1e9;
int del = dep[y] - dep[x];
for(int i = 20; i >= 0; i--) {
if(del & (1 << i)) {
ans = std::min(ans, mn[y][i]);
y = anc[y][i];
}
}
if(x == y) return ans;
for(int i = 20; i >= 0; i--) {
if(anc[x][i] != anc[y][i]) {
ans = std::min(ans, mn[x][i]);
x = anc[x][i];
ans = std::min(ans, mn[y][i]);
y = anc[y][i];
}
}
ans = std::min(ans, std::min(mn[x][0], mn[y][0]));
return ans;
}
int q, x, y;
int main() {
n = readint(); m = readint();
for(int i = 1; i <= n; i++) {
fa[i] = i;
}
for(int i = 1; i <= m; i++) {
edges[i].u = readint(); edges[i].v = readint(); edges[i].w = readint();
}
std::sort(edges + 1, edges + m + 1, cmp);
kruskal();
for(int i = 1; i <= n; i++) {
if(!dep[i]) {
dep[i] = 1;
dfs(i);
}
}
calanc();
q = readint();
while(q--) {
x = readint(); y = readint();
int f1 = find(x), f2 = find(y);
if(f1 != f2) puts("-1");
else printf("%d\n", query(x, y));
}
return 0;
}