最小生成树

1.prim

每次循环都访问一个点，并将此点所有边找到其最小的边权，如果最小边权对应的点没有被访问过，则加入队列。这相当于向生成树中添加了n-1条最小边，最后检查所有点的连通性，联通的话得到的就是最小生成树，属于贪心算法。

暴力贪心的话复杂度为o(n²)，这边采用堆优化的方法，时间复杂度o(mlogn)

 1 const int N = 2e5 + 10, INF = 0x3f3f3f3f3f3f3f3f;
 2 int dis[N];
 3 bool vis[N];
 4 int n, m, sum;
 5 vector<pair<int, int>> vt[N];
 6 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> q;
 7 int prim(int pos) {
 8     int ans = 0;
 9     int cnt = 0;
10     q.push(make_pair(0, pos));
11     while (!q.empty() && cnt <= n) {
12         int x = q.top().first;
13         int y = q.top().second;
14         q.pop();
15         if (vis[y])continue;
16         vis[y] = true;
17         ans += x; cnt++;
18         for (auto it : vt[y])
19             if (!vis[it.first])
20                 q.push(make_pair(it.second, it.first));
21     }
22     return ans;
23 }
24 void solve() {
25     cin >> n >> m;
26     memset(dis, INF, sizeof(dis));
27     for (int i = 1; i <= m; i++) {
28         int u, v, w;
29         cin >> u >> v >> w;
30         vt[u].push_back(make_pair(v, w));
31         vt[v].push_back(make_pair(u, w));
32     }
33     int value = prim(1);
34     int flag = 0;
35     for (int i = 1; i <= n; i++)
36         if (!vis[i])flag = 1;
37     if (value >= INF || flag)cout << "orz" << endl;
38     else cout << value << endl;
39 }

跟最短路的代码有些相似。

2、kruskal

将所有边进行排序后利用并查集将点连成一个集合，最后检查一下所有点是否在同一个集合内，是的话则输出最小生成树。

 1 const int N = 2e5 + 10, INF = 0x3f3f3f3f3f3f3f3f;
 2 int f[N];
 3 int n, m, sum;
 4 struct edge {
 5     int u, v, w;
 6 }ed[N];
 7 void start() {
 8     for (int i = 1; i <= n; i++)f[i] = i;
 9 }
10 bool cmp(edge k, edge l) {
11     return k.w < l.w;
12 }
13 int find(int x) {
14     if (x == f[x])return x;
15     f[x] = find(f[x]);
16     return f[x];
17 }
18 int kruskal() {
19     int ans = 0;
20     int cnt = 0;
21     for (int i = 1; i <= m; i++){
22         int fu = find(ed[i].u);
23         int fv = find(ed[i].v);
24         if (fu != fv) {
25             f[fu] = fv;
26             ans += ed[i].w;
27             cnt++;
28         }
29         if (cnt == n - 1)return ans;
30     }
31     return -1;
32 }
33 void solve() {
34     cin >> n >> m;
35     start();
36     for (int i = 1; i <= m; i++)
37         cin >> ed[i].u >> ed[i].v >> ed[i].w;
38     sort(ed + 1, ed + 1 + m, cmp);
39     int temp = kruskal();
40     int cnt = 0;
41     for (int i = 1; i <= n; i++)
42         if (f[i] == i)cnt++;
43     if (cnt > 1)temp = -1;
44     if (temp != -1)cout << temp << endl;
45     else cout << "orz" << endl;
46 }