【題目鏈接】

ybt 1392：繁忙的都市(city)
洛谷 P2330 [SCOI2005]繁忙的都市

【題目考點】

1. 圖論 最小生成樹

【解題思路】

將題目敘述轉為圖論概念，交叉路口為頂點，道路為邊，道路是雙向的，且所有交叉路口都直接或間接連接起來，說明這是無向連通圖。每條道路的分值，就是邊的權值。政府要改造一些道路，就是選一些邊。
三個要求的概念分別為：

選擇的邊構成的圖應該是連通圖，且應該包含原圖所有頂點。

選擇的邊盡可能少。
邊最少時，該圖就成了無根樹。邊數為頂點數減1。
綜合以上兩點，選擇的邊及頂點構成的圖就是原圖的生成樹。

生成樹有多種方案，選擇其中權值最大的邊最小的那一種生成樹方案，即瓶頸生成樹。

樹上最大邊權值在圖的所有生成樹中最小的生成樹，叫做瓶頸生成樹。
最小生成樹一定是瓶頸生成樹，但瓶頸生成樹未必是最小生成樹。（其證明見百度百科）

題目要求的就是瓶頸生成樹，我們可以直接求出最小生成樹，它一定是瓶頸生成樹。
該題頂點數<=300，邊數<=100000，使用Prim，Prim堆優化，Kruskal都可以完成該題。

【題解代碼】

解法1：樸素Prim算法

#include<bits/stdc++.h> using namespace std; #define N 305 struct Edge {int t, w;Edge(){}Edge(int a, int b):t(a),w(b){}; }; vector<Edge> edge[N]; bool vis[N]; int n, m, mx; int dis[N]; void initGraph() {int f, t, w;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> f >> t >> w;edge[f].push_back(Edge(t, w));edge[t].push_back(Edge(f, w));} } void prim() {memset(dis, 0x3f, sizeof(dis));dis[1] = 0;for(int k = 1; k <= n; ++k){int u = 0;for(int i = 1; i <= n; ++i){if(vis[i] == false && (u == 0 || dis[i] < dis[u]))u = i;}vis[u] = true;mx = max(mx, dis[u]);for(int i = 0; i < edge[u].size(); ++i){int v = edge[u][i].t, w = edge[u][i].w;if(vis[v] == false && dis[v] > w)dis[v] = w;}} } int main() {initGraph();prim();cout << n-1 << ' ' << mx;return 0; }

解法2：Prim算法堆優化

#include<bits/stdc++.h> using namespace std; #define N 305 struct Pair {int v, d;Pair(){}Pair(int a, int b):v(a),d(b){}bool operator < (const Pair &b) const{return b.d < d;} }; struct Edge {int t, w;Edge(){}Edge(int a, int b):t(a),w(b){}; }; vector<Edge> edge[N]; bool vis[N]; int n, m, mx; int dis[N]; void initGraph() {int f, t, w;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> f >> t >> w;edge[f].push_back(Edge(t, w));edge[t].push_back(Edge(f, w));} } void prim() {memset(dis, 0x3f, sizeof(dis));priority_queue<Pair> pq;pq.push(Pair(1, 0));dis[1] = 0;while(pq.empty() == false){int u = pq.top().v;pq.pop();if(vis[u])continue;vis[u] = true;mx = max(mx, dis[u]);for(int i = 0; i < edge[u].size(); ++i){int v = edge[u][i].t, w = edge[u][i].w;if(vis[v] == false && dis[v] > w){dis[v] = w;pq.push(Pair(v, dis[v]));}}} } int main() {initGraph();prim();cout << n-1 << ' ' << mx;return 0; }

解法2：Kruskal算法

#include<bits/stdc++.h> using namespace std; #define N 305 struct Edge {int f, t, w;Edge(){}Edge(int a, int b, int c):f(a),t(b),w(c){};bool operator < (const Edge &b) const{return w < b.w;} }; vector<Edge> edges; bool vis[N]; int fa[N]; int n, m, mx, en; void initFa() {for(int i = 1; i <= n; ++i)fa[i] = i; } int find(int x) {return x == fa[x] ? x : (fa[x] = find(fa[x])); } void merge(int x, int y) {fa[find(x)] = find(y); } void init() {int f, t, w;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> f >> t >> w;edges.push_back(Edge(f, t, w));} } void kruskal() {sort(edges.begin(), edges.end());for(int i = 0; i < edges.size(); ++i){int f = edges[i].f, t = edges[i].t, w = edges[i].w;if(find(f) != find(t)){merge(f, t);mx = max(mx, w);if(++en == n - 1)break;}} } int main() {init();initFa();kruskal();cout << n-1 << ' ' << mx;return 0; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1392：繁忙的都市(city) | 洛谷 P2330 [SCOI2005]繁忙的都市的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。