网站服务器繁忙是怎么回事,模仿淘宝详情页做网站,wild合成版是哪个网站做的,视觉设计的特点和优势*原题链接*
最小瓶颈生成树题#xff0c;和货车运输完全一样。
先简化题意#xff0c; 次询问#xff0c;每次给出 #xff0c;问 到 的所有路径集合中#xff0c;最小边权的最大值。
对于这种题可以用kruskal生成树来做#xff0c;也可以用倍增来写#xff0c;但不…*原题链接*
最小瓶颈生成树题和货车运输完全一样。
先简化题意 次询问每次给出 问 到 的所有路径集合中最小边权的最大值。
对于这种题可以用kruskal生成树来做也可以用倍增来写但不管怎样都要先求出最大生成树因为最小边权的最大值肯定会在最大生成树中出现。然后我们要做的就是在树中求 到 的最短路径上的最小边权。这个可以倍增求求解的过程类似求 lca。
#includebits/stdc.h
using namespace std;
const int N1e510,M3e510,INF0x3f3f3f3f;int read(){int x0,f1;char chgetchar();while(!isdigit(ch)){if(ch-) f-1;chgetchar();}while(isdigit(ch)) xx*10ch-0,chgetchar();return x*f;
}int n,m,q,head[N],tot,f[N],fa[N][20],dep[N],fm[N][20];
struct node{int from,to,nxt,w;
}e[M*2],edge[M*2];
void add(int x,int y,int w){edge[tot].toy;edge[tot].ww;edge[tot].nxthead[x];head[x]tot;
}
bool cmp(node a,node b){return a.wb.w;
}int find(int x){if(x!f[x]) f[x]find(f[x]);return f[x];
}void kruskal(){for(int i1;in;i) f[i]i;sort(e1,e1m,cmp);for(int i1;im;i){int xfind(e[i].from),yfind(e[i].to);if(xy) continue;f[x]y,add(e[i].from,e[i].to,e[i].w),add(e[i].to,e[i].from,e[i].w);}
}void dfs(int x,int father){dep[x]dep[father]1,fa[x][0]father;for(int ihead[x];i;iedge[i].nxt){int yedge[i].to;if(yfather) continue;fm[y][0]edge[i].w;dfs(y,x);}
}void init(){for(int i1;(1i)n;i){for(int j1;jn;j){fa[j][i]fa[fa[j][i-1]][i-1];fm[j][i]min(fm[j][i-1],fm[fa[j][i-1]][i-1]);}}
}int lca(int x,int y){if(dep[x]dep[y]) swap(x,y);int klog2(dep[y]1),ansINF;for(int ik;i0;i--){if(dep[y]-(1i)dep[x]) ansmin(ans,fm[y][i]),yfa[y][i];}if(xy) return ans;for(int ik;i0;i--){if(fa[x][i]!fa[y][i]){ansmin(ans,min(fm[x][i],fm[y][i]));xfa[x][i],yfa[y][i];}}return min(ans,min(fm[x][0],fm[y][0]));
}int main(){nread(),mread(),qread();for(int i1;im;i){int xread(),yread(),wread();e[i]{x,y,0,w};}kruskal(),memset(fm,0x3f,sizeof(fm)),dfs(1,0),init();while(q--){int xread(),yread();if(find(x)!find(y)) cout-1endl;else coutlca(x,y)endl;}return 0;
}
