Network
Time Limit: 10 Sec Memory Limit: 128 MB
[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 < = 15,000)。
每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少？
图中有M条边 (1 <= M <= 30,000) ，第j条边的长度为： d_j ( 1 < = d_j < = 1,000,000,000).
现在有 K个询问 (1 < = K < = 15,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点的所有路径中，最长的边最小值是多少？
第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
1 <= M <= 30,000
1 <= d_j <= 1,000,000,000
1 <= K <= 15,000
题解：
最小生成树算法
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct qer
{
int from, to, cost;
}q[50005];
struct qer2
{ int to, d;
}qq[100005];
int fa[100005], t[20005][20], d[20005][20], la[20005], lb[20005], tot = 0;
int first[100005], next[100005];
bool cmp(qer a, qer b)
{
return a.cost < b.cost;
}
void build(int f, int t, int d)
{
qq[++tot].to = t;
qq[tot].d = d;
next[tot] = first[f];
first[f] = tot;
}
int find(int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool orzqer(int x,int y)
{
return la[x] < la[y];
}
void dfs(int u)
{
int v;
for(int i = first[u];i;i = next[i])
{
v = qq[i].to;
if(!la[v])
{
la[v] = la[u] + 1;
t[v][0] = u;
d[v][0] = qq[i].d;
dfs(v);
}
}
}
int ask(int u, int v)
{
if(la[u] > la[v])
swap(u, v);
int tt = la[v] - la[u];
int ans = 0;
for(int i = 0;i <= 15;i ++)
{
if(tt>>i & 1)
{
ans = max(ans,d[v][i]);
v = t[v][i];
}
}
for(int i = 15;i >= 0;i --)
{
if(t[v][i] != t[u][i])
{
ans = max(ans,d[v][i]);
ans = max(ans,d[u][i]);
v = t[v][i];
u = t[u][i];
}
}
if(u != v)
{
ans = max(ans, d[u][0]);
ans = max(ans, d[v][0]);
}
return ans;
}
int main()
{
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for(int i = 1;i <= n;i ++)
{
fa[i] = i;
lb[i] = i;
}
for(int i = 1;i <= m;i ++)
{
scanf("%d%d%d", &q[i].from, &q[i].to, &q[i].cost);
}
sort(q + 1,q + m + 1, cmp);
int x, y;
for(int i = 1;i <= m;i ++)
{
x = q[i].from;
y = q[i].to;
if(find(x) != find(y))
{
build(x, y, q[i].cost);
build(y, x, q[i].cost);
fa[find(x)] = find(y);
}
}
for(int i = 1;i <= n;i ++)
{
if(!la[i])
{
la[i] = 1;
dfs(i);
t[i][0] = i;
}
}
sort(lb+1, lb+n+1, orzqer);
for(int i = 1;i <= n; i ++)
for(int j = 1;j <= 15;j ++)
{
x = lb[i];
y = t[x][j-1];
t[x][j] = t[y][j-1];
d[x][j] = max(d[x][j-1],d[y][j-1]);
}
for(int i = 1;i <= k;i ++)
{
scanf("%d%d", &x, &y);
printf("%d\n", ask(x,y));
}
return 0;
}