训练指南UVA11354（最小生成树+倍增LCA）

layout: post
title: 训练指南 UVA - 11354&＃xff08;最小生成树 &＃43; 倍增LCA&＃xff09;
author: "luowentaoaa"
catalog: true
mathjax: true
tags:
- 最小生成树
- LCA
- 图论
- 训练指南

Bond

UVA - 11354

题意

给你一张无向图&＃xff0c;然后有若干组询问&＃xff0c;让你输出a->b的最小瓶颈路

题解

先求出最小生成树,然后对这个最小生成树做LCA。

#include
using namespace std;
typedef long long ll;
const ll mod&＃61;998244353;
const int maxn&＃61;1e5&＃43;50;
const int logmaxn&＃61;20;
const ll inf&＃61;0x3f3f3f3f3f3f3f3fLL;
struct LCA{int n;int fa[maxn]; ///父亲数组int cost[maxn]; ///和父亲的费用int L[maxn]; ///层次(根节点为0)int anc[maxn][logmaxn]; /// anc[p][i]是结点p的第2^i级父亲。anc[i][0] &＃61; fa[i]int maxcost[maxn][logmaxn]; /// maxcost[p][i]是i和anc[p][i]的路径上的最大费用void preprocess(){for(int i&＃61;0;i&＃61;0;i--)if(L[p]-(1<&＃61;L[q]){ans&＃61;max(ans,maxcost[p][i]);p&＃61;anc[p][i];}if(p&＃61;&＃61;q)return ans; ///LCA为pfor(int i&＃61;log;i>&＃61;0;i--)if(anc[p][i]!&＃61;-1&&anc[p][i]!&＃61;anc[q][i]){ans&＃61;max(ans,maxcost[p][i]);p&＃61;anc[p][i];ans&＃61;max(ans,maxcost[q][i]);q&＃61;anc[q][i];}ans&＃61;max(ans,cost[p]);ans&＃61;max(ans,cost[q]);return ans; ///LCA为fa[p]&＃xff08;它也等于fa[q]&＃xff09;}
};
LCA solver;
int pa[maxn];
int findset(int x){return pa[x]!&＃61;x?pa[x]&＃61;findset(pa[x]):x;}
vectorG[maxn],C[maxn];
void dfs(int u,int fa,int level){solver.L[u]&＃61;level;for(int i&＃61;0;i}struct Edge{int x,y,d;bool operator <(const Edge& rhs)const{return d};
const int maxm&＃61;1e5&＃43;10;
Edge e[maxm];int main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int kase&＃61;0,n,m,x,y,d,Q;while(cin>>n>>m){for(int i&＃61;0;i>x>>y>>d;e[i]&＃61;(Edge){x-1,y-1,d};}sort(e,e&＃43;m);for(int i&＃61;0;i>Q;while(Q--){cin>>x>>y;cout<}