首页 > 代码库 > BZOJ3732: Network

BZOJ3732: Network

2024-07-25 09:16:50   208人阅读

3732: Network

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 89  Solved: 30
[Submit][Status]

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 

 

Source

题解：

裸倍增。。。

终于能1A这种题了 ，交的时候忽然想到万一图不连通就被坑死了，结果A了，还是出题人比较良心。。。

代码：

  1 #include<cstdio>  2 #include<cstdlib>  3 #include<cmath>  4 #include<cstring>  5 #include<algorithm>  6 #include<iostream>  7 #include<vector>  8 #include<map>  9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 100000 14 #define maxm 100000 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define mod 1000000007 23 using namespace std; 24 inline int read() 25 { 26     int x=0,f=1;char ch=getchar(); 27     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 28     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 29     return x*f; 30 } 31 int n,m,k,head[maxn],tot,fa[maxn],f[maxn][20],g[maxn][20],dep[maxn]; 32 struct rec{int x,y,w;}a[maxm]; 33 struct edge{int go,next,w;}e[2*maxn]; 34 inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}; 35 inline void insert(int x,int y,int z) 36 { 37     e[++tot].go=y;e[tot].next=head[x];e[tot].w=z;head[x]=tot; 38     e[++tot].go=x;e[tot].next=head[y];e[tot].w=z;head[y]=tot; 39 } 40 inline bool cmp(rec a,rec b) 41 { 42     return a.w<b.w; 43 } 44 void dfs(int x) 45 { 46     for1(i,15) 47      if((1<<i)<=dep[x]) 48       { 49           int y=f[x][i-1]; 50           f[x][i]=f[y][i-1]; 51           g[x][i]=max(g[x][i-1],g[y][i-1]); 52       } 53      else break; 54     for(int i=head[x],y;i;i=e[i].next) 55      if(!dep[y=e[i].go]) 56       { 57           dep[y]=dep[x]+1; 58         f[y][0]=x;g[y][0]=e[i].w; 59         dfs(y); 60       } 61 } 62 int query(int x,int y) 63 { 64     int ans=0; 65     if(dep[x]<dep[y])swap(x,y); 66     int t=dep[x]-dep[y]; 67     for0(i,15) 68      if(t&(1<<i)) 69       { 70           ans=max(ans,g[x][i]);x=f[x][i]; 71       } 72     if(x==y)return ans;   73     for3(i,15,0) 74      if(f[x][i]!=f[y][i]) 75       { 76         ans=max(ans,g[x][i]);x=f[x][i]; 77         ans=max(ans,g[y][i]);y=f[y][i]; 78       } 79     ans=max(ans,max(g[x][0],g[y][0])); 80     return ans; 81 } 82 int main() 83 { 84     freopen("input.txt","r",stdin); 85     freopen("output.txt","w",stdout); 86     n=read();m=read();k=read(); 87     for1(i,m)a[i].x=read(),a[i].y=read(),a[i].w=read(); 88     sort(a+1,a+m+1,cmp); 89     for1(i,n)fa[i]=i; 90     int j=1; 91     for1(i,n-1) 92     { 93         while(find(a[j].x)==find(a[j].y))j++; 94         fa[find(a[j].x)]=find(a[j].y); 95         insert(a[j].x,a[j].y,a[j].w); 96         j++; 97     } 98     dep[1]=1; 99     dfs(1);100     while(k--)printf("%d\n",query(read(),read()));101     return 0;102 }
View Code

 

BZOJ3732: Network


联系
我们