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

审题本题需要我们在满足三个条件的前提下选路修整并输出方案中所有道路数和权值最大的那条道路的权值思路方法一瓶颈生成树-》最小生成树题目条件分析给定一个无重边双向连通图条件1所有节点都要处于连通状态条件2选定的边尽可能少生成树条件3要求方案中的权值最大的边的权值尽可能小根据这三个条件我们判断出题目要求的是瓶颈生成树权值最大的边的权值最小的生成树而瓶颈生成树和最小生成树是完全一样的所以我们使用kruskal算法解决问题只要注意ret是最大权值并维护好ret即可解题#includeiostream #includealgorithm 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] 繁忙的都市 - 洛谷