代碼實現-鄰接矩陣：

#include <bits/stdc++.h>
using namespace std;const int N = 5010, INF = 0x3f3f3f3f;int n, m;
int edges[N][N]; //鄰接矩陣int dist[N]; //某個點距離生成樹的最短距離
bool st[N]; //標記哪些點已經加入到生成樹int prim()
{//初始化memset(dist, 0x3f, sizeof dist);dist[1] = 0;int ret = 0;for (int i = 1; i <= n; i++) //循環加入n個點{//1.找最近點int t = 0;for (int j = 1; j <= n; j++)if (!st[j] && dist[j] < dist[t])t = j;//判斷是否連通if (dist[t] == INF) return INF;st[t] = true;ret += dist[t];//2.更新距離for (int j = 1; j <= n; j++) //枚舉t能走到哪{dist[j] = min(dist[j], edges[t][j]);}}return ret;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;//初始化為無窮memset(edges, 0x3f, sizeof edges);for (int i = 1; i <= m; i++){int x, y, z; cin >> x >> y >> z;//有重邊求最小值edges[x][y] = edges[y][x] = min(edges[x][y], z);}int ret = prim();if (ret == INF) cout << "orz" << endl;else cout << ret << endl;return 0;
}

代碼實現-鄰接表-vector數組：

#include <bits/stdc++.h>
using namespace std;typedef pair<int, int> PII;const int N = 5010, INF = 0x3f3f3f3f;int n, m;
vector<PII> edges[N];int dist[N];
bool st[N];int prim()
{memset (dist, 0x3f, sizeof dist);dist[1] = 0;int ret = 0;for (int i = 1; i <= n; i++){//1.找最近點int t = 0;for (int j = 1; j <= n; j++)if (!st[j] && dist[j] < dist[t])t = j;//判斷是否連通if (dist[t] == INF) return INF;st[t] = true;ret += dist[t];//2.更新距離for (auto& p : edges[t]){int a = p.first, b = p.second;//t->a,權值是bdist[a] = min(dist[a], b);}}return  ret;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= m; i++){int x, y, z; cin >> x >> y >> z;edges[x].push_back({y,z});edges[y].push_back({x,z});}int ret = prim();if (ret == INF) cout << "orz" << endl;else cout << ret << endl;return 0;
}

題?轉化：

• 如果把每?個零?看成?個節點，優惠看成?條邊，就變成在圖中找最??成樹的問題。
• 因此，跑?遍kk算法即可。
  注意：

1. 存邊的時候，沒有必要存重復的，并且權值過?的也不需要存；
2. 最終提取結果的時候，雖然有可能構造不出來?棵最??成樹，但是要在已有的構造情況下處理結果

#include <bits/stdc++.h>
using namespace std;const int N = 500 * 500 + 10;int a, n;int pos;
struct node
{int x, y, z;
}e[N];int fa[N];int find (int x)
{return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}int cnt, ret;bool cmp(node& a, node& b)
{return a.z < b.z;
}void kk()
{sort(e+1, e+1+pos, cmp);for (int i = 1; i <= pos; i++){int x = e[i].x, y = e[i].y, z = e[i].z;int fx = find(x), fy = find(y);if (fx != fy){cnt++;ret += z;fa[fx] = fy;}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> a >> n;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++){int k; cin >> k;if (i >= j || k > a || k == 0) continue;pos++;e[pos].x = i; e[pos].y = j; e[pos].z = k;}for (int i = 1; i <= n; i++) fa[i] = i;kk();cout << ret + (n - cnt) * a << endl;return 0;
}

定理：最??成樹就是瓶頸?成樹。
在kk算法中，維護邊權的最?值即可

#include <bits/stdc++.h>
using namespace std;const int N = 310, M = 8010;int n, m;
struct node
{int x, y, z;
}e[M];int fa[N];int find (int x)
{return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}int ret; //最大邊的權值bool cmp(node& x, node& y)
{return x.z < y.z;
}void kk()
{for (int i = 1; i <= n; i++) fa[i] = i;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);fa[fx] = fy;}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= m; i++) cin >> e[i].x >> e[i].y >> e[i].z;cout << n - 1 << " ";kk();cout << ret << endl;return 0;
}

第?問：從起點開始，做?次dfs/bfs就可以掃描到所有的點。
第?問：因為有回溯的效果，相當于就是選擇?些邊，把所有的點都連接起來。但是需要注意：

• 由于這些邊是有?向的，我們只要保證能從1位置出發，訪問到所有的點即可。與最??成樹還是有差異的。
• 為了能保證選出來的邊能夠從1訪問所有點，應該優先考慮去往更?位置的邊，這樣才能向下?到更低的位置

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
typedef pair<int, int> PII;const int N = 1e5 + 10, M = 2e6 + 10;int n, m;
int h[N];vector<PII> edges[N];int fa[N];int find(int x)
{return fa[x] == x ? x : fa[x] = find(fa[x]);
}LL cnt, ret;
bool st[N];int pos;
struct node
{int x, y, z;  
}e[M];void dfs(int u)
{cnt++;st[u] = true;for (auto& p : edges[u]){int v = p.first, k = p.second;pos++;e[pos].x = u; e[pos].y = v; e[pos].z = k;if (!st[v]) dfs(v);}
}bool cmp(node& a, node& b)
{int y1 = a.y, z1 = a.z, y2 = b.y, z2 = b.z;if (h[y1] != h[y2]) return h[y1] > h[y2];else return z1 < z2;
}void kk()
{for (int i = 1; i <= n; i++) fa[i] = i;sort (e+1, e+1+pos, cmp);for (int i = 1; i <= pos; 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 += z;fa[fx] = fy;}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> h[i];for (int i = 1; i <= m; i++){int x, y, z; cin >> x >> y >> z;    if (h[x] >= h[y]) edges[x].push_back({y, z});if (h[x] <= h[y]) edges[y].push_back({x, z});}dfs(1);cout << cnt << " ";kk();cout << ret << endl;return 0;
}