题解 UVA10048 【噪音恐惧症】

### 前言： [$ \large{}\color {#6495ED} \mathcal{MyBlog} $](https://xjx885.coding-pages.com/) 发现没有人发克鲁斯卡尔重构树的题解诶... 于是过来发一发... （话说我为什么要给这种规模的题写克鲁斯卡尔重构树啊0.0） --- ### 题目大意： 给定一张无向图，多次求两个点之间路径上最大权值最小是多少... --- ### 题目分析: Emmm...最大权值最小....果断克鲁斯卡尔重构树0.0... 啥是克鲁斯卡尔重构树？ 首先，你得熟练掌握最小生成树中的克鲁斯卡尔算法... 然后，你得知道...无向图的最小生成树一定是最小瓶颈生成树 没理解？出门左转[洛谷日报 克鲁斯卡尔重构树详解](https://www.luogu.org/blog/user9012/ke-lu-si-ka-er-zhong-gou-shu-lve-xie) 我直接说具体操作... 首先，克鲁斯卡尔算法选定一条边E时，加入一个点V，权值为这条边... 把E链接的两个连通块的顶点A,B的父亲设为V，并把A,V和B,V之间连边... 这一操作完毕之后...询问a,b路径上最长边最小值时，直接输出a,b的LCA的权值就好... 具体细节见代码 --- ### 代码： ```cpp #include <bits/stdc++.h> using namespace std; const int N = 110; int C, S, Q; //克鲁斯卡尔需要的边 struct node { int a, b, c; node (int aa, int bb, int cc) { a = aa, b = bb, c = cc; } node () { } bool operator < (const node & other ) const { return c < other.c; } }; vector <node > Link; //并查集 int fa[N * 3]; int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } //克鲁斯卡尔重构树 int f[N * 3][10]; int d[N * 3], deep[N * 3]; vector <int > link[N * 3]; int n; void Kruskal() { sort(Link.begin(), Link.end()); n = C; for(int k = 0; k < (int )Link.size(); k++) { int a = Link[k].a, b = Link[k].b, c = Link[k].c; if(find(a) != find(b)) { int top_a = fa[a], top_b = fa[b]; //把两个连通块的顶点的父亲设为新加节点 fa[top_a] = fa[top_b] = ++n; //把两个连通块的顶点的父亲与新加节点连边 link[n].push_back(top_a); link[n].push_back(top_b); //新加节点权值设为该边边权 d[n] = c; } } } //倍增LCA预处理 void dfs(int wz, int fa) { deep[wz] = deep[fa] + 1, f[wz][0] = fa; for(int k = 1; k < 10; k++) f[wz][k] = f[f[wz][k - 1]][k - 1]; for(int k = 0; k < (int )link[wz].size(); k++) { int to = link[wz][k]; dfs(to, wz); } } //倍增LCA int LCA(int a, int b) { if(deep[a] < deep[b]) swap(a, b); for(int k = 9; k >= 0; k--) if(deep[a] - (1 << k) >= deep[b]) a = f[a][k]; if(a == b) return d[a]; for(int k = 9; k >= 0; k--) if(f[a][k] != f[b][k]) a = f[a][k], b = f[b][k]; return d[f[a][0]]; } int main() { int opt = 0; while(scanf("%d %d %d", &C, &S, &Q)) { if(C == 0) break; memset(deep, 0, sizeof(deep)); memset(link, 0, sizeof(link)); Link.clear(); if(opt++ != 0) printf("\n"); printf("Case #%d\n", opt); for(int k = 1; k <= C * 3; k++) fa[k] = k; for(int k = 1; k <= S; k++) { int c1, c2, d; scanf("%d %d %d", &c1, &c2, &d); Link.push_back(node(c1, c2, d)); } Kruskal(); for(int k = 1; k <= n; k++) if(!deep[k]) dfs(find(k), 0); for(int k = 1; k <= Q; k++) { int c1, c2; scanf("%d %d", &c1, &c2); if(find(c1) == find(c2)) printf("%d\n", LCA(c1, c2)); else printf("no path\n"); } } return 0; } ``` --- ### 结语： 如果本题解有BUG... 那么...那么...那么... （随意了）还请私信作者.... --- ## END