3732: Network
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2812 Solved: 1363
[Submit][Status][Discuss]
Description
给你N个点的无向图 (1 <= N <= 15,000)，记为：1…N。
图中有M条边 (1 <= M <= 30,000) ，第j条边的长度为： d_j ( 1 < = d_j < = 1,000,000,000).
现在有 K个询问 (1 < = K < = 20,000)。
每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少？
Input
第一行： N, M, K。
第2..M+1行: 三个正整数：X, Y, and D (1 <= X <=N; 1 <= Y <= N). 表示X与Y之间有一条长度为D的边。
第M+2..M+K+1行: 每行两个整数A B,表示询问从A点走到B点的所有路径中，最长的边最小值是多少？
Output
对每个询问，输出最长的边最小值是多少。
Sample Input
6 6 8
1 2 5
2 3 4
3 4 3
1 4 8
2 5 7
4 6 2
1 2
1 3
1 4
2 3
2 4
5 1
6 2
6 1
1 2 5
2 3 4
3 4 3
1 4 8
2 5 7
4 6 2
1 2
1 3
1 4
2 3
2 4
5 1
6 2
6 1
Sample Output
5
5
5
4
4
7
4
5
5
5
4
4
7
4
5
HINT
1 <= N <= 15,000
1 <= M <= 30,000
1 <= d_j <= 1,000,000,000
1 <= K <= 15,000
Solution
看到题想到的是前几年noip考的货车运输，就是建出最大生成树再链剖+线段树求链上最小边即可，学习了一波$Kruskal$重构树后，整道题就直接变成最大生成树+求LCA了！
这道题是模板了，大佬%%%写的相当清楚了，在最小生成树连接两个块时，新建一个点，作为两个块最远祖先（并查集中）的父亲节点，把这条边的权值下放到新建节点的点权，因为这条边就是连接两个块的最长边权的最小值，所以每次询问返回两个点的LCA的点权值即可。
再也不用复杂的线段树或者倍增啦！！！
Code
#include<bits/stdc++.h>
using namespace std; int n, m, k; struct Node {
int u, v, nex, w;
} Edge1[], Edge[];
bool cmp(Node a, Node b) { return a.w < b.w; } int stot1;
void add1(int u, int v, int w) {
Edge1[++stot1] = (Node) {u, v, , w};
} int stot, h[];
void add(int u, int v) {
Edge[++stot] = (Node) {u, v, h[u], };
h[u] = stot;
} int u_fa[];
int find(int u) {
if(u != u_fa[u]) u_fa[u] = find(u_fa[u]);
return u_fa[u];
} int t, val[];
void Kruskal() {
for(int i = ; i <= n * ; i ++) u_fa[i] = i;
t = n;
for(int i = ; i <= m; i ++) {
int u = Edge1[i].u, v = Edge1[i].v, w = Edge1[i].w;
int uu = find(u), vv = find(v);
if(uu != vv) {
u_fa[uu] = ++ t; u_fa[vv] = t;
add(t, uu); add(t, vv); val[t] = w;
}
}
} int siz[], fa[], son[], dep[];
void dfs1(int u, int ff) {
fa[u] = ff; siz[u] = ; dep[u] = dep[ff] + ;
for(int i = h[u]; i; i = Edge[i].nex) {
int v = Edge[i].v;
if(v == ff) continue;
dfs1(v, u);
siz[u] += siz[v];
if(siz[v] > siz[son[u]]) son[u] = v;
}
} int top[];
void dfs2(int u, int tp) {
top[u] = tp;
if(son[u]) dfs2(son[u], tp);
for(int i = h[u]; i; i = Edge[i].nex) {
int v = Edge[i].v;
if(v == son[u] || v == fa[u]) continue;
dfs2(v, v);
}
} int LCA(int u, int v) {
if(find(u) != find(v)) return ;
while(top[u] != top[v]) {
if(dep[top[u]] < dep[top[v]]) swap(u, v);
u = fa[top[u]];
}
if(dep[u] < dep[v]) swap(u, v);
return val[v];
} int main() {
scanf("%d%d%d", &n, &m, &k);
for(int i = ; i <= m; i ++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add1(u, v, w);
}
sort(Edge1 + , Edge1 + + m, cmp);
Kruskal();
for(int i = ; i <= t; i ++)
if(!dep[i]) {
dfs1(u_fa[i], ); dfs2(u_fa[i], u_fa[i]);
}
for(int i = ; i <= k; i ++) {
int u, v;
scanf("%d%d", &u, &v);
printf("%d\n", LCA(u, v));
}
return ;
}