BZOJ——T 3732: Network

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

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1880 Solved: 894
[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

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

Source

最小生成树+倍增

 #include <algorithm>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int N(+);

 const int M(+);

 int n,m,k;

 #define LL long long

 int head[N],sumedge;

 struct E

 {

     int u,v,w;

 }e[M];

 bool cmp(E a,E b)

 {

     return a.w<b.w;

 }

 struct Edge

 {

     int v,next;

     LL dis;

     Edge(int v=,int next=,LL dis=):

         v(v),next(next),dis(dis){}

 }edge[];

 inline void ins(int u,int v,LL w)

 {

     edge[++sumedge]=Edge(v,head[u],w);

     head[u]=sumedge;

 }

 int fa[N],cnt;

 int find(int x)

 {

     return x==fa[x]?x:fa[x]=find(fa[x]);

 }

 void Kruskar()

 {

     sort(e+,e+m+,cmp);

     for(int i=;i<=n;i++) fa[i]=i;

     for(int i=;i<=m;i++)

     {

         int x=e[i].u,y=e[i].v;

         int fx=find(x),fy=find(y);

         if(fa[fx]==fy) continue;

         fa[fx]=fy;

         ins(x,y,(LL)e[i].w);

         ins(y,x,(LL)e[i].w);

         if(++cnt==n-) return ;

     }

 }

 LL maxx[N];

 int dad[N],deep[N];

 void DFS(int x)

 {

     deep[x]=deep[dad[x]]+;

     for(int i=head[x];i;i=edge[i].next)

     {

         int v=edge[i].v;

         if(dad[x]==v) continue;

         maxx[v]=edge[i].dis;

         dad[v]=x; DFS(v);

     }

 }

 LL LCA(int x,int y)

 {

     LL ret=-;

     if(deep[x]>deep[y]) swap(x,y);

     for(;deep[y]>deep[x];y=dad[y]) ret=max(ret,maxx[y]);

     for(;x!=y;x=dad[x],y=dad[y])

          ret=max(ret,max(maxx[x],maxx[y]));

     return ret;

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&k);

     memset(maxx,-,sizeof(maxx));

     for(int u,v,w,i=;i<=m;i++)

         scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

     Kruskar();

     DFS();

     for(int u,v;k--;)

     {

         scanf("%d%d",&u,&v);

         printf("%lld\n",LCA(u,v));

     }

     return ;

 }

巴特西