BZOJ 3732: Network 最小生成树 倍增

3732: Network

题目连接:

http://www.lydsy.com/JudgeOnline/problem.php?id=3732

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点的所有路径中,最长的边最小值是多少?

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

Sample Output

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

题意

题解:

求最小生成树之后,查询链上最大边的权值。

树链剖分或者倍增都可以。

代码

#include<bits/stdc++.h>
using namespace std; const int N=200500;
int n,m;
struct node
{
int x,y,c,no;
}E[N<<1];
int pre[N],to[N<<1],w[N<<1],nxt[N<<1],k;
int fa[N],lca[N][22],p[N][22],dep[N],cnt; void makeedge(int x,int y,int c)
{
to[cnt]=x;w[cnt]=c;nxt[cnt]=pre[y];pre[y]=cnt++;
to[cnt]=y;w[cnt]=c;nxt[cnt]=pre[x];pre[x]=cnt++;
}
int getfather(int x)
{
if(fa[x]==x) return fa[x];else return fa[x]=getfather(fa[x]);
}
void dfs(int x)
{
for(int it=pre[x];~it;it=nxt[it])
{
int y=to[it],c=w[it];
if(y==lca[x][0]) continue;
dep[y]=dep[x]+1,lca[y][0]=x,p[y][0]=c;
dfs(y);
}
}
int query(int x,int y)
{
int ret=0;
if(dep[x]<dep[y]) swap(x,y);
for(int i=21;i>=0;i--)
if(dep[x]-(1<<i)>=dep[y])
ret=max(ret,p[x][i]),x=lca[x][i];
if(x==y) return ret;
for(int i=21;i>=0;i--)
if(lca[x][i]!=lca[y][i])
ret=max(ret,max(p[x][i],p[y][i])),x=lca[x][i],y=lca[y][i];
ret=max(ret,max(p[y][0],p[x][0]));
return ret;
}
bool cmp(node t1,node t2)
{
return t1.c<t2.c;
} int main()
{
scanf("%d%d%d",&n,&m,&k);
memset(pre,-1,sizeof(pre));
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].c);
E[i].no=i;
}
sort(E+1,E+m+1,cmp);
long long tot=0;
for(int i=1;i<=m;i++)
{
int x=E[i].x,y=E[i].y;
int f1=getfather(x),f2=getfather(y);
if(f1!=f2)
{
fa[f2]=f1;
tot+=(long long)E[i].c;
makeedge(x,y,E[i].c);
}
}
dfs(1);
for(int j=1;j<=21;j++)
for(int i=1;i<=n;i++)
if(lca[i][j-1])
{
lca[i][j]=lca[lca[i][j-1]][j-1];
p[i][j]=max(p[i][j-1],p[lca[i][j-1]][j-1]);
}
for(int i=1;i<=k;i++)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",query(x,y));
}
}
上一篇:通过easyui tab添加的子页面JS脚本必须放在body才生效


下一篇:Easyui Tab刷新