简述四大行业的网站推广方式,做财务还是网站运营,网站建设方案ppt模板,建网站联系电话*原题链接*
最小瓶颈生成树题#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;
}
