【题意】
n个点m条边的图 q次询问 找到一条从s到t的一条边 使所有边的最大危险系数最小
Input
There will be at most 5 cases in the input file.
The first line of each case contains two integers N, M (2 ≤ N ≤ 50000, 1 ≤ M ≤ 100000) – number
of cities and roads. The next M lines describe the roads. The i-th of these lines contains three integers:
xi, yi, di (1 ≤ xi, yi ≤ N, 0 ≤ di ≤ 10^9) – the numbers of the cities connected by the i-th road and its
dangerousness.
Description of the roads is followed by a line containing an integer Q (1 ≤ Q ≤ 50000), followed by
Q lines, the i-th of which contains two integers si and ti (1 ≤ si
, ti ≤ N, si ̸= ti).
Consecutive input sets are separated by a blank line.
Output
For each case, output Q lines, the i-th of which contains the minimum dangerousness of a path between
cities si and ti
. Consecutive output blocks are separated by a blank line.
The input file will be such that there will always be at least one valid path.
Sample Input
4 5
1 2 10
1 3 20
1 4 100
2 4 30
3 4 10
2
1 4
4 1
2 1
1 2 100
1
1 2
Sample Output
20
20
100
【分析】
很明显是最小瓶颈生成树。
有一个定理：最小生成树是最小瓶颈生成树，但是最小瓶颈生成树不一定是最小生成树。
我们只要求最小生成树就好了。
不过这题n较大，不能n^2预处理，所以我们先把树求出来，然后询问的时候 树剖或者倍增 都可以。
应该是，倍增耗空间但是时间少一个log ， 树剖省一点空间但是 时间多一个log （要多一个数据结构维护）
我上次就打一题倍增MLE了TAT，不过这题正解是倍增，不知道树剖+线段树能不能过。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 50010
#define Maxm 1000010
#define INF 0xfffffff struct node
{
int x,y,c,next;
}t[Maxn*],tt[Maxm];
int len;
int first[Maxn]; bool cmp(node x,node y) {return x.c<y.c;}
int mymax(int x,int y) {return x>y?x:y;} int fa[Maxn];
int ffind(int x)
{
if(fa[x]!=x) fa[x]=ffind(fa[x]);
return fa[x];
} void ins(int x,int y,int c)
{
t[++len].x=x;t[len].y=y;t[len].c=c;
t[len].next=first[x];first[x]=len;
} int f[Maxn][],g[Maxn][],dep[Maxn]; void dfs(int x,int ff,int l)
{
dep[x]=dep[ff]+;
g[x][]=ff;
for(int i=;(<<i)<=dep[x];i++)
g[x][i]=g[g[x][i-]][i-];
f[x][]=l;
for(int i=;(<<i)<=dep[x];i++)
f[x][i]=mymax(f[x][i-],f[g[x][i-]][i-]);
for(int i=first[x];i;i=t[i].next) if(t[i].y!=ff)
dfs(t[i].y,x,t[i].c);
} int ffind(int x,int y)
{
int ans=;
while(dep[x]!=dep[y])
{
int z;
if(dep[x]<dep[y]) z=x,x=y,y=z;
for(int i=;i>=;i--) if(dep[x]-(<<i)>=dep[y])
ans=mymax(ans,f[x][i]),x=g[x][i];
}
if(x==y) return ans;
if(x!=y)
{
for(int i=;i>=;i--) if(g[x][i]!=g[y][i]&&dep[x]>=(<<i))
ans=mymax(ans,f[x][i]),ans=mymax(ans,f[y][i]),
x=g[x][i],y=g[y][i];
}
ans=mymax(ans,f[x][]);ans=mymax(ans,f[y][]);
return ans;
} int main()
{
int n,m;
bool ok=;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(ok) printf("\n");
ok=;
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&tt[i].x,&tt[i].y,&tt[i].c);
}
sort(tt+,tt++m,cmp);
int cnt=;
for(int i=;i<=n;i++) fa[i]=i;
len=;
memset(first,,sizeof(first));
for(int i=;i<=m;i++)
{
if(ffind(tt[i].x)!=ffind(tt[i].y))
{
fa[ffind(tt[i].x)]=ffind(tt[i].y);
cnt++;
ins(tt[i].x,tt[i].y,tt[i].c);
ins(tt[i].y,tt[i].x,tt[i].c);
}
if(cnt==n-) break;
}
dep[]=;
dfs(,,);
int q;
scanf("%d",&q);
for(int i=;i<=q;i++)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",ffind(x,y));
}
}
return ;
}
2016-11-01 08:16:45