農夫約翰要把他的牛奶運輸到各個銷售點。
運輸過程中，可以先把牛奶運輸到一些銷售點，再由這些銷售點分别運輸到其他銷售點。
運輸的總距離越小，運輸的成本也就越低。
低成本的運輸是農夫約翰所希望的。
不過，他并不想讓他的競争對手知道他具體的運輸方案，是以他希望采用費用第二小的運輸方案而不是最小的。
現在請你幫忙找到該運輸方案。
注意：：
- 如果兩個方案至少有一條邊不同，則我們認為是不同方案；
- 費用第二小的方案在數值上一定要嚴格大于費用最小的方案；
- 答案保證一定有解；
輸入格式
第一行是兩個整數 N,M，表示銷售點數和交通線路數；
接下來 MM 行每行 33 個整數 x,y,z，表示銷售點 x 和銷售點 y 之間存線上路，長度為 z。
輸出格式
輸出費用第二小的運輸方案的運輸總距離。
資料範圍
1≤N≤500,
1≤M≤104,
1≤z≤109,
資料中可能包含重邊。
輸入樣例：
輸出樣例：4 4 1 2 100 2 4 200 2 3 250 3 4 100450
次小生成樹定義：在圖中的所有生成樹中，權值之和第二小的樹：
非嚴格次小生成數：權值第一小的生成樹和第二小的生成樹權值相同
嚴格次小生成數：權值第二小的生成樹嚴格大于權值第一小的生成樹
次小生成樹的求法：
方法一：先求最小生成樹，再枚舉删除最小生成樹的邊，然後加上非最小生成樹的邊：
此方法隻能求非嚴格次小生成樹
方法二：先求最小生成樹，然後依次枚舉非樹邊，将非樹邊加入樹中，同時樹中去掉一條邊，使得最終的圖仍是一顆樹：
此方法不僅可以求非嚴格次小生成樹，也可以求嚴格次小生成樹
是以我們着重介紹方法二
方法二解法：
設T為圖G的一顆生成樹，對于非樹邊a和樹邊b，插入邊a和删除邊b的操作記為（ + a, - b）.
如果T + a - b之後，仍是一顆生成樹稱（+ a , - b）是T的一個可行交換。
稱由T進行一次可行變換所得到的新的生成樹集合稱為T的鄰集。
定理：此小生成樹一定在鄰集中
解決步驟：
1：假設樹中的權值總和為res則需要求（res + w - 樹邊的最大值/次大值）使得他最小，其中w表示非樹邊的值
2：為何要求最大與次大？？因為怕樹中的最大值與非樹邊相同，但是次大值肯定小于最大值
求最小生成樹。
3：記錄其中的樹邊，然後求出最小生成樹中任意兩個點a, b之間的路徑的最大值與次大值，然後依次枚舉每條非樹邊用于替換樹邊，找出替換後的大于最小生成樹的權值的最小值即為嚴格次小生成樹
方法二代碼：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 510, M = 10010; int n, m; int p[N]; int dist1[N][N], dist2[N][N];//dist1記錄最小值，dist2記錄次小值 int h[N], e[M], ne[M], w[M], idx;//鄰接表記錄的是樹邊 struct Edge { int a, b, w; bool is_tree; bool operator < (const Edge &W) const { return w < W.w; } }edges[M]; void add(int a, int b, int c)//鄰接表 { e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx; idx ++ ; } int find(int x)//并查集 { if (p[x] != x) p[x] = find(p[x]); return p[x]; } void dfs(int u, int fa, int max1, int max2, int d1[], int d2[]) { d1[u] = max1, d2[u] = max2; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (j != fa) { int r1 = max1, r2 = max2; if (w[i] > r1)//若目前枚舉的權值大于最大值 { r2 = r1;//将最大值置為次大值 r1 = w[i];//将w[i]置為最大值 } else if (w[i] > r2 && w[i] < r1) r2 = w[i];//若目前枚舉的權值大于次大值 dfs(j, u, r1, r2, d1, d2);//枚舉下一個點 } } } int main() { cin >> n >> m; for (int i = 1; i <= n; i ++ ) p[i] = i; memset(h, -1, sizeof h); for (int i = 0; i < m; i ++ ) { int a, b, c; scanf("%d %d %d", &a, &b, &c); edges[i] = {a, b, c}; } sort(edges, edges + m); LL sum = 0; for (int i = 0; i < m; i ++ )//求出最小生成樹 { int a = edges[i].a, b = edges[i].b, w = edges[i].w; int pa = find(a), pb = find(b); if (pa != pb) { p[pa] = pb; sum += w; edges[i].is_tree = true;//将i加入樹邊 add(a, b, w), add(b, a, w); } } for (int i = 1; i <= n; i ++ ) dfs(i, -1, -1e9, -1e9, dist1[i], dist2[i]); //找出樹邊中從點i走到各個點的路徑的最大值 LL res = 1e18; for (int i = 0; i < m; i ++ ) if (!edges[i].is_tree)//枚舉非樹邊 { int a = edges[i].a, b = edges[i].b, w = edges[i].w; LL max1 = dist1[a][b], max2 = dist2[a][b];//記錄樹中最大值與次大值 if (w > max1) res = min(res, sum + w - max1);//若最大值可以被更新 else if (w > max2) res = min(res, sum + w - max2);//若最大值不可以更新但次大值可以更新 } cout << res << endl; return 0; }
方法三：時間複雜度O(m)
步驟：
1：先求出最小生成樹，并記錄樹中的總權值sum。
2：預處理三個數組記錄的是樹邊，fa[i][j], d1[i][j], d2[i][j]。fa[i][j]表示從點 i 跳2^j 步之後所跳到達的點為fa[i][j]。d1[i][j], d2[i][j]分别為從 i 點開始跳2 ^ j步之後所到達的點fa[i][j]中路徑的最大值與次大值
1：先求出最小生成樹。
3：枚舉每條非樹邊a, b，權值為w。在最小生成樹中找出 a 到 b 的最大的權值假設為d，找出sum + w - d他的值為大于sum的最小值即為嚴格最小生成樹
方法三代碼如下：
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 100010, M = 300010, INF = 0x3f3f3f3f; int n, m; int p[N]; int depth[N]; int fa[N][17]; int d1[N][17], d2[N][17]; int h[N], e[M], ne[M], w[M], idx; struct Edge { int a, b, w; bool used; bool operator < (const Edge &W) const { return w < W.w; } }edge[M]; void add(int a, int b, int c)//鄰接表 { e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx; idx ++ ; } int find(int x)//并查集 { if (p[x] != x) p[x] = find(p[x]); return p[x]; } void bfs() { queue<int> q; memset(depth, 0x3f, sizeof depth); depth[0] = 0, depth[1] = 1;//設定邊界，若不了解看推薦的部落格 q.push(1);//這裡以任意點為根節點都可以，我這裡假設的是以1為根節點 while (q.size()) { int t = q.front(); q.pop(); for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (depth[j] > depth[t] + 1)//若j還未被更新 { depth[j] = depth[t] + 1; fa[j][0] = t;//j往上跳2^0為點t q.push(j); d1[j][0] = w[i], d2[j][0] = -INF;//最大值為w[i]，要求次大值沒有初始化為-INF. for (int k = 1; k <= 16; k ++ ) { int anc = fa[j][k - 1]; fa[j][k] = fa[anc][k - 1]; int distance[4] = {d1[j][k - 1], d2[j][k - 1], d1[anc][k - 1], d2[anc][k - 1]}; //[j, j + 2 ^ k]步直接的最大值必在以上四個值中 d1[j][k] = -INF, d2[j][k] = -INF;//要求的是最大值是以初始化為負無窮 for (int u = 0; u < 4; u ++ ) { int d = distance[u]; if (d > d1[j][k])//若可以更新最大值 { d2[j][k] = d1[j][k]; d1[j][k] = d; } else if (d2[j][k] < d && d < d1[j][k]) d2[j][k] = d;//若可以更新次大值，注意要嚴格小于最大值 } } } } } } LL lca(int a, int b, int w) { if (a == b) return INF; if (depth[a] < depth[b]) swap(a, b);//保證a所在的位置比b深好進行下面操作 int cnt = 0; static int distance[N * 2];//要記錄次大值與最大值是以大小為2 * N；用static是為了節省空間 for (int k = 16; k >= 0; k -- )//将a節點跳到與b同一層的深度 if (depth[fa[a][k]] >= depth[b])//若a跳2^k的深度大于b的深度則将a跳過去 { distance[cnt ++ ] = d1[a][k];//記錄[a, a + 2 ^ k]路徑之間的值 distance[cnt ++ ] = d2[a][k];//要先紀律順序不能反否則a會被更新 a = fa[a][k];//将a跳到fa[a][k] } if (a != b)//說明他們跳到同一深度後還不是同一節點 { for (int k = 16; k >= 0; k -- )//将a, b跳到a, b的最近公共祖先的下一層 if (fa[a][k] != fa[b][k]) { distance[cnt ++ ] = d1[a][k];//記錄a, b的最大與次大值 distance[cnt ++ ] = d2[a][k]; distance[cnt ++ ] = d1[b][k]; distance[cnt ++ ] = d2[b][k]; a = fa[a][k]; b = fa[b][k]; } distance[cnt ++ ] = d1[a][0]; distance[cnt ++ ] = d2[a][0]; distance[cnt ++ ] = d1[b][0]; distance[cnt ++ ] = d2[b][0]; } LL max1 = -INF, max2 = -INF;//找出最大值與次大值 for (int i = 0; i < cnt; i ++ ) { if (distance[i] > max1)//若最大值可被更新 { max2 = max1; max1 = distance[i]; } else if (max2 < distance[i] && distance[i] < max1) max2 = distance[i];//次大值可被更新 } if (w > max1) return w - max1;//找出符合條件的w - max1的最小值然後加上main函數裡的sum即為 if (w > max2) return w - max2;//最小生成樹 return INF;//說明不存在可以被更新次小生成樹。 } LL kruscal() { LL res = 0; sort(edge, edge + m); memset(h, -1, sizeof h); for (int i = 1; i <= n; i ++ ) p[i] = i; for (int i = 0; i < m; i ++ ) { int a = edge[i].a, b = edge[i].b, w = edge[i].w; int fa = find(a), fb = find(b); if (fa != fb) { p[fa] = fb; res += w; edge[i].used = true; add(a, b, w), add(b, a, w); } } return res; } int main() { cin >> n >> m; for (int i = 0; i < m; i ++ ) { int a, b, c; scanf("%d %d %d", &a, &b, &c); edge[i] = {a, b, c}; } LL sum = kruscal();//求最小生成樹 bfs();//預處理fa, d1, d2數組 LL res = 1e18; for (int i = 0; i < m; i ++ ) if (!edge[i].used)//枚舉分數邊 { int a = edge[i].a, b = edge[i].b, w = edge[i].w; res = min(res, sum + lca(a, b, w));//找出大于sum的最小值即次小生成樹 } cout << res << endl; return 0; }
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)