算法题（236）：繁忙的都市

审题：

本题需要我们在满足三个条件的前提下选路修整，并输出方案中所有道路数和权值最大的那条道路的权值

思路：
方法一：瓶颈生成树-》最小生成树

题目条件分析：给定一个无重边，双向连通图

条件1：所有节点都要处于连通状态

条件2：选定的边尽可能少（生成树）

条件3：要求方案中的权值最大的边的权值尽可能小

根据这三个条件我们判断出题目要求的是瓶颈生成树（权值最大的边的权值最小的生成树），而瓶颈生成树和最小生成树是完全一样的，所以我们使用kruskal算法解决问题，只要注意ret是最大权值，并维护好ret即可

解题：

#include<iostream> #include<algorithm> using namespace std; const int N = 310, M = 8010; int n, m,ret;//ret表示瓶颈生成树的最大权值边 int f[N]; struct edge { int x, y, z; }e[M]; bool cmp(edge& a, edge& b) { return a.z < b.z; } int find(int num) { return f[num] == num ? num : f[num] = find(f[num]); } void kruskal() { sort(e + 1, e + 1 + m,cmp); for (int i = 1; i <= m; i++) { int x = e[i].x, y = e[i].y, z = e[i].z; int fx = find(x), fy = find(y); if (fx != fy) { ret = max(ret, z); f[fx] = fy; } } } int main() { cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> e[i].x >> e[i].y >> e[i].z; } //初始化并查集 for (int i = 1; i <= n; i++) { f[i] = i; } kruskal(); cout << n - 1 << " " << ret << endl; return 0; }

注意1：

题目中说明了是连通图，所以一定有最小生成树，不用维护cnt来进行特殊判断

P2330 [SCOI2005] 繁忙的都市 - 洛谷