3732: Network
题目：传送门
题解：
第一眼就看到最大边最小，直接一波最小生成树。
一开始还担心会错，问了一波肉大佬，任意两点在最小生成树上的路径最大边一定是最小的。
那么事情就变得简单起来了嘿嘿嘿，建棵树，直接在线LCA啊，用一个mx[i][j]记录i往上2^j这段区间的最大值。
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 struct node 8 { 9 ????int x,y,c;10 }a[111000];int len;11 void ins(int x,int y,int c)12 {13 ????len++;a[len].x=x;a[len].y=y;a[len].c=c;14 }15 struct edge16 {17 ????int x,y,c,next;18 }e[111000];int llen,last[15100];19 void inss(int x,int y,int c)20 {21 ????llen++;e[llen].x=x;e[llen].y=y;e[llen].c=c;22 ????e[llen].next=last[x];last[x]=llen;23 }24 int fa[15100];25 int findfa(int x){if(fa[x]!=x)fa[x]=findfa(fa[x]);return fa[x];}26 bool cmp(node n1,node n2){return n1.c<n2.c;}27 int n,m,T;28 int bin[21],dep[15100],f[15100][21];29 int mx[15100][21];//记录i~i+2^j的最大边值 30 void pre_tree_node(int x)31 {32 ????for(int i=1;i<=20 && dep[x]>=bin[i];i++)33 ????????f[x][i]=f[f[x][i-1]][i-1],mx[x][i]=max(mx[x][i-1],mx[f[x][i-1]][i-1]);34 ????for(int k=last[x];k;k=e[k].next)35 ????{36 ????????int y=e[k].y;37 ????????if(y!=f[x][0])38 ????????{39 ????????????dep[y]=dep[x]+1;40 ????????????f[y][0]=x;mx[y][0]=e[k].c;41 ????????????pre_tree_node(y);42 ????????}43 ????}44 }45 int sol(int x,int y)46 {47 ????int maxx=0;48 ????if(dep[x]<dep[y])swap(x,y);49 ????for(int i=20;i>=0;i--)50 ????????if(dep[x]-dep[y]>=bin[i])51 ????????????maxx=max(maxx,mx[x][i]),x=f[x][i];52 ????if(x==y)return maxx;53 ????for(int i=20;i>=0;i--)54 ????????if(dep[x]>=bin[i] && f[x][i]!=f[y][i])55 ????????????maxx=max(maxx,max(mx[x][i],mx[y][i])),x=f[x][i],y=f[y][i];56 ????maxx=max(maxx,max(mx[x][0],mx[y][0]));57 ????return maxx;58 }59 int main()60 {61 ????bin[0]=1;for(int i=1;i<=20;i++)bin[i]=bin[i-1]<<1;62 ????scanf("%d%d%d",&n,&m,&T);63 ????llen=len=0;memset(last,0,sizeof(last));64 ????for(int i=1;i<=m;i++)65 ????{66 ????????int x,y,c;scanf("%d%d%d",&x,&y,&c);67 ????????ins(x,y,c);ins(y,x,c);68 ????}69 ????sort(a+1,a+len+1,cmp);70 ????for(int i=1;i<=n;i++)fa[i]=i;int tt=0;71 ????for(int i=1;i<=len;i++)72 ????{73 ????????int fx=findfa(a[i].x),fy=findfa(a[i].y);74 ????????if(fx!=fy)75 ????????{76 ????????????fa[fy]=fx,tt++;77 ????????????inss(a[i].x,a[i].y,a[i].c);78 ????????????inss(a[i].y,a[i].x,a[i].c);79 ????????????if(tt==n-1)break;80 ????????}81 ????}82 ????for(int i=1;i<=n;i++)83 ????????if(fa[i]==i)84 ????????????f[i][0]=0,dep[i]=1,pre_tree_node(i);85 ????while(T--)86 ????{87 ????????int st,ed;scanf("%d%d",&st,&ed);88 ????????printf("%d\n",sol(st,ed));89 ????}90 ????return 0;91 }bzoj3732: Network(最小生成树+LCA)
原文地址：https://www.cnblogs.com/CHerish_OI/p/8634261.html