首页 > 代码库 > bzoj3732Network

bzoj3732Network

bzoj3732Network

题意:

给一个无向图,k个询问求节点a到节点b最长边的最小值。n,k≤15000。

题解:

”最长边的最小值“经常可以用最小生成树解决,因为生成树里的每一条边都是可取的最小边,求完生成树之后就是经典的倍增应用:求lca的时候顺便维护一下边权最大值即可。

代码:

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <queue>
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 #define maxn 30010
 7 using namespace std;
 8 
 9 inline int read(){
10     char ch=getchar(); int f=1,x=0;
11     while(ch<0||ch>9){if(ch==-)f=-1; ch=getchar();}
12     while(ch>=0&&ch<=9)x=x*10+ch-0,ch=getchar();
13     return f*x;    
14 }
15 struct abc{int f,t,w;}abcd[maxn]; bool cmp(abc a,abc b){return a.w<b.w;}
16 struct e{int t,w,n;}es[maxn*2]; int g[maxn],ess;
17 void pe(int f,int t,int w){
18     es[++ess]=(e){t,w,g[f]}; g[f]=ess; es[++ess]=(e){f,w,g[t]}; g[t]=ess;
19 }
20 int n,m,k,p[maxn],fa[20][maxn],mx[20][maxn],tot,dep[maxn];
21 int find(int x){return x==p[x]?x:p[x]=find(p[x]);}
22 void dfs(int x){
23     for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa[0][x])
24         fa[0][es[i].t]=x,mx[0][es[i].t]=es[i].w,dep[es[i].t]=dep[x]+1,dfs(es[i].t);
25 }
26 int lca(int x,int y){
27     if(dep[x]<dep[y])swap(x,y); int t=dep[x]-dep[y],ans=0;
28     for(int i=0;(1<<i)<=n;i++)if(t&(1<<i))ans=max(ans,mx[i][x]),x=fa[i][x];
29     for(int i=19;i>=0;i--)if(fa[i][x]!=fa[i][y])
30         ans=max(ans,mx[i][x]),ans=max(ans,mx[i][y]),x=fa[i][x],y=fa[i][y];
31     if(x==y)return ans;else{ans=max(ans,mx[0][x]); ans=max(ans,mx[0][y]); return ans;}
32 }
33 int main(){
34     n=read(); m=read(); k=read(); inc(i,1,n)p[i]=i;
35     inc(i,1,m){int x=read(),y=read(),z=read(); abcd[i]=(abc){x,y,z};} sort(abcd+1,abcd+m+1,cmp);
36     inc(i,1,m){
37         int x=find(abcd[i].f),y=find(abcd[i].t); if(x!=y)pe(x,y,abcd[i].w),p[x]=y,tot++; if(tot==n-1)break;
38     }
39     dfs(1);
40     for(int i=1;(1<<i)<=n;i++)inc(j,1,n)
41         fa[i][j]=fa[i-1][fa[i-1][j]],mx[i][j]=max(mx[i-1][j],mx[i-1][fa[i-1][j]]);
42     inc(i,1,k){int x=read(),y=read(); printf("%d\n",lca(x,y));}
43     return 0;
44 }

 

20161115

bzoj3732Network