这是一道写起来比较顺手的题目
没有各种奇怪的细节,基本就是Kruskal和倍增LCA的模板。。
题目大意:对于一个无向带权图,询问两点之间一条路,使得这条路上的最长边最小,输出最小最长边的的值
那么既然要使最长边最短,我们可以先构造一棵最小生成树
由于kruskal已经将边排了序了,所以对于这棵树,每条边都尽量最短了
然后我们再进行lca求出两点路径上的最长边,即为答案
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; ; struct node{ int u,v,cost,next; }e[maxn*],et[maxn*]; int head[maxn],n,m,K,tot,logn,u,v; ],mx[maxn][]; void insert(int u, int v, int c){ e[++tot].u=u; e[tot].v=v; e[tot].cost=c; e[tot].next=head[u]; head[u]=tot; } bool cmp(node a, node b){ return a.cost<b.cost; } int find(int x){ return f[x]==x?x:f[x]=find(f[x]); } void MST(){ ; i<=n; i++) f[i]=i; ; i<=m; i++){ int fx=find(et[i].u), fy=find(et[i].v); if (fx!=fy){ f[fy]=fx; insert(et[i].u,et[i].v,et[i].cost); insert(et[i].v,et[i].u,et[i].cost); } } } void dfs(int u, int f, int d, int cost){ dep[u]=d; fa[u][]=f; mx[u][]=cost; ; i<=logn; i++) fa[u][i]=fa[fa[u][i-]][i-]; ; i<=logn; i++) mx[u][i]=max(mx[u][i-],mx[fa[u][i-]][i-]); ; i=e[i].next) ,e[i].cost); } int lca_max(int u, int v){ ; if (dep[u]>dep[v]) swap(u,v); while (dep[u]<dep[v]){ ; i--) if (dep[u]<dep[fa[v][i]]){ ans=max(ans,mx[v][i]); v=fa[v][i]; } ans=max(ans,mx[v][]); v=fa[v][]; } if (u==v) return ans; ; i--){ if (fa[u][i]!=fa[v][i]){ ans=max(ans,max(mx[v][i],mx[u][i])); u=fa[u][i]; v=fa[v][i]; } } ans=max(ans,max(mx[u][],mx[v][])); return ans; } int main(){ scanf("%d%d%d", &n, &m, &K); tot=-; memset(head,-,sizeof(head)); <<logn)<n) logn++; ; i<=m; i++) scanf("%d%d%d", &et[i].u, &et[i].v, &et[i].cost); sort(et+,et++m,cmp); MST(); dfs(,,,); while (K--){ scanf("%d%d", &u, &v); printf("%d\n", lca_max(u,v)); } ; }