题意:给你一张无向图,然后有若干组询问,让你输出a->b的最小瓶颈路。
思路:又是一道最小瓶颈路的题目。以前做过单组询问的,由郭华阳在集训队论文里提到的性质。在单组询问的时候只需要求出kurskal算大过程中第一次将他们合并的边就好了。但是对于这道题的多组询问,我们就不能那么处理了。在郭华阳的论文里讲到了一种方法每次合并时生成一个节点,把待合并的两个集合看成两颗子树,这样最终我们就只要对于询问的两个节点,求出他LCA的权值即可。
如图所示。但是这里我所采用的是另一种方法。就是dis[i][j]数组维护的是j号结点到2^i祖先的瓶颈路。这样我们把lca的查询过程稍稍修改一下就可以了。
代码如下:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <cstring> 6 #include <algorithm> 7 #include <queue> 8 #include <stack> 9 #include <vector> 10 #include <set> 11 #include <map> 12 #define MP(a, b) make_pair(a, b) 13 #define PB(a) push_back(a) 14 15 using namespace std; 16 17 typedef long long ll; 18 typedef pair<int ,int> pii; 19 typedef pair<unsigned int, unsigned int> puu; 20 typedef pair<int ,double> pid; 21 typedef pair<ll, int> pli; 22 typedef pair<int, ll> pil; 23 24 const int INF = 0x3f3f3f3f; 25 const double eps = 1e-6; 26 const int LEN = 100000+10; 27 const int LOG_LEN = 25; 28 struct edge{int from, to;ll val;}; 29 vector<pil> Map[LEN]; 30 edge e[LEN]; 31 int n, m, fa[LEN], q, qa, qb, parent[LOG_LEN][LEN], depth[LEN]; 32 ll dis[LOG_LEN][LEN]; 33 bool cmp(edge a, edge b){return a.val<b.val;} 34 //UFSET 35 void init(){for(int i=0; i<LEN; i++)fa[i] = i;} 36 int Find(int a){return fa[a]==a?a:Find(fa[a]);} 37 void Union(int a, int b){int pa = Find(a), pb = Find(b);if(pa!=pb)fa[pa] = pb;} 38 39 //Use Kruskal to build MST 40 void Kruskal() 41 { 42 sort(e, e+m, cmp); 43 init(); 44 int cnt = 0; 45 for(int i=0; i<m; i++){ 46 int a = e[i].from, b = e[i].to; 47 ll v = e[i].val; 48 if(Find(a) == Find(b))continue; 49 Union(a, b); 50 Map[a].PB(MP(b,v)); 51 Map[b].PB(MP(a,v)); 52 cnt++; 53 if(cnt == n-1) return ; 54 } 55 } 56 57 //LCA 58 void dfs(int v, int f, int d) 59 { 60 parent[0][v] = f; 61 dis[0][v] = -1; 62 depth[v] = d; 63 for(int i=0; i<Map[v].size(); i++){ 64 pil nv = Map[v][i]; 65 if(nv.first!=f) dfs(nv.first, v, d+1); 66 else dis[0][v] = nv.second; 67 } 68 } 69 70 void init_lca() 71 { 72 memset(dis, 0, sizeof dis); 73 memset(depth, -1, sizeof depth); 74 for(int i=1; i<=n; i++)if(depth[i]<0)dfs(i, -1, 0); 75 for(int k=0; k+1<LOG_LEN; k++){ 76 for(int i=1; i<=n; i++){ 77 if(parent[k][i]<0) parent[k+1][i] = dis[k+1][i] = -1; 78 else { 79 parent[k+1][i] = parent[k][parent[k][i]]; 80 dis[k+1][i] = max(dis[k][i], dis[k][parent[k][i]]); 81 } 82 } 83 } 84 } 85 86 ll lca(int u, int v) 87 { 88 if(depth[v] > depth[u]) swap(u, v); 89 ll ret = 0; 90 for(int i=0; i<LOG_LEN; i++){ 91 if((depth[u]-depth[v]) >> i & 1) { 92 ret = max(ret, dis[i][u]); 93 u = parent[i][u]; 94 } 95 } 96 if(u==v) return ret; 97 for(int i=LOG_LEN-1; i>=0; i--){ 98 if(parent[i][u]!=parent[i][v]){ 99 ret = max(ret, dis[i][u]); 100 ret = max(ret, dis[i][v]); 101 u = parent[i][u];v = parent[i][v]; 102 } 103 } 104 ret = max(ret, dis[0][u]); 105 ret = max(ret, dis[0][v]); 106 return ret; 107 } 108 109 int main() 110 { 111 // freopen("in.txt", "r", stdin); 112 113 int kase = 1; 114 while(scanf("%d%d", &n, &m)!=EOF) 115 { 116 kase == 1? kase++:puts(""); 117 for(int i=0; i<LEN; i++)Map[i].clear(); 118 for(int i=0; i<m; i++)scanf("%d%d%lld", &e[i].from, &e[i].to, &e[i].val); 119 Kruskal(); 120 init_lca(); 121 scanf("%d", &q); 122 for(int i=0; i<q; i++){ 123 scanf("%d%d", &qa, &qb); 124 printf("%lld\n", lca(qa, qb)); 125 } 126 } 127 return 0; 128 }