图论：最小生成树

最小生成树 （无向无环图）

概念

1.Prim算法 P3366 【模板】最小生成树 - 洛谷

邻接矩阵实现 

#include<iostream>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 5e3 + 10;
int dis[N]; //记录每个结点到其他结点的巨鹿
bool st[N];//记录每个节点是否被遍历过int edge[N][N];//记录每个结点到其他结点的巨鹿int n, m;//prim算法实现
int prim()
{//把dis初始化成无穷大memset(dis, INF, sizeof(dis));dis[1] = 0;//第一个结点开头int ret = 0;for (int i = 1; i <= n; i++){int t = 0;//找最近点for (int j = 1; j <= n; j++){if (!st[j] && dis[j] < dis[t])t = j;//更新最小值的下标}//判断是否联通if (dis[t] == INF)return INF;//把该点加进去st[t] = true;ret += dis[t];//更新disfor (int i = 1; i <= n; i++){if (dis[i] > edge[t][i])//如果距离大于新的结点距离其他节点的距离，更新dis[i] = edge[t][i];}}return ret;
}int main()
{cin >> n >> m;memset(edge, INF, sizeof(edge));for (int i = 1; i <= m; i++){int x, y, z; cin >> x >> y >> z;//注意有重边的情况，注意是取笑，初始化为无穷大edge[x][y] = edge[y][x] = min(edge[x][y], z);}int ret = prim();if (ret == INF)cout << "orz" << endl;elsecout << ret << endl;
}

 vector数组实现

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;typedef pair<int, int> PII;//连接的点，权值
const int INF = 0x3f3f3f3f;
const int N = 5e3 + 10;int n, m;
int dis[N];
bool st[N];
vector<PII> dp[N];int prim()
{memset(dis, INF, sizeof(dis));dis[1] = 0;int ret = 0;for (int i = 1; i <= n; i++)//加入n个点，功德圆满{//找最近的点int t = 0;//dis[0]给初始化成INF了for (int j = 1; j<= n; j++){if (!st[j] && dis[j] < dis[t])//没有被访问过并且比t小，更新t{t = j;}}//判断是否联通if (dis[t] == INF)return INF;st[t] = true;ret += dis[t];//更新disfor (auto& x : dp[t]){int a = x.first;//相连的点int b = x.second;//相连的点的权值/*if (dis[a] > b)dis[a] = b;*/dis[a] = min(dis[a], b);//这里可以解决重边的情况}}return ret;
}int main()
{cin >> n >> m;for (int i = 1; i <= m; i++){int x, y, z; cin >> x >> y >> z;dp[x].push_back({ y,z });dp[y].push_back({ x,z });}int ret = prim();if (ret == INF)cout << "orz" << endl;elsecout << ret << endl;
}

2.克鲁斯卡尔算法（并查集实现）

P3366 【模板】最小生成树 - 洛谷

#include<iostream>
#include<algorithm>
using namespace std;const int N = 5010;//点
const int M = 2e5 + 10;//边
const int INF = 0x3f3f3f3f;struct node
{int x, y, z;
}a[M];int f[N];//并查集
int n, m;int find(int x)
{return f[x] == x ? x : f[x] = find(f[x]);
}
void un(int x, int y)
{f[find(x)] = find(y);
}bool cmp(node& x, node& y)
{return x.z < y.z;
}int kruskal()
{int ret = 0;int cnt = 0;for (int i = 1; i <= m; i++){int x = a[i].x, y = a[i].y, z = a[i].z;if (find(x) != find(y))//没有并在一起，就整{cnt++;//记录边的个数，最小生成树，节点数n，边数n-1ret += z;un(x, y);}}if (cnt != n-1)return INF;//成功的话是n - 1,没有说明不联通return ret;
}int main()
{cin >> n >> m;for (int i = 1; i <= m; i++){cin >> a[i].x >> a[i].y >> a[i].z;}//并查集初始化for (int i = 1; i <= n; i++)f[i] = i;//排序，从小到大sort(a + 1, a + 1 + m, cmp);int ret = kruskal();if (ret == INF)cout << "orz" << endl;elsecout << ret << endl;
}

P1194 买礼物 - 洛谷

#include<iostream>
#include<algorithm>
using namespace std;const int N = 500*500+10;//结点*结点 == 边的个数，我们存的是边的个数
const int M = 1010;
int a, n;//A和节点数
int pos;//有几条边要存
int f[N];//并查集struct node
{int x, y, z;
}b[N];//存边之间的个数bool cmp(node& x, node& y)//排序
{return x.z < y.z;
}int find(int x)
{return f[x] == x ? x : f[x] = find(f[x]);
}
//克鲁斯卡尔算法
int kk()
{int ret = 0;//总价int cnt = 0;//几条边，用来计算分成几块，有几块就*多少个Afor (int i = 1; i <= pos; i++){int x = b[i].x, y = b[i].y, z = b[i].z;//取出边的数据int fx = find(x);int fy = find(y);if (fx != fy && z < a && z != 0){ret += z;cnt++;//计算有多少条边f[find(x)] = find(y);//合并}}ret += (n - cnt) * a;//有几块树return ret;
}int main()
{cin >> a >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){int k; cin >> k;//只需要存一条边的关系//但其实就算不要也无所谓，因为并查集合并后，也不会要重复的//克鲁斯卡尔算法只需要存取，边的数据就好了，不重复更好if (i >= j)continue;pos++;b[pos].x = i, b[pos].y = j, b[pos].z = k;}}for (int i = 1; i <= n; i++)f[i] = i;sort(b + 1, b + 1 + pos,cmp);int ret = kk();cout << ret << endl;
}

P2330 [SCOI2005] 繁忙的都市 - 洛谷

瓶颈树：生成所有生成树中，最大边权值最小的那棵树。

也就是最小生成树。

最小生成树的最大边值也就是最终结果

#include<iostream>
#include<algorithm>
using namespace std;const int N = 310;
const int M = 8010;
int n, m;
int pos;
int f[N];struct node
{int x, y, z;
}a[M];int find(int x)
{return f[x] == x ? x : f[x] = find(f[x]);
}bool cmp(node& x, node& y)
{return x.z < y.z;
}int ret = 0;
void kk()
{for (int i = 1; i <= m; i++){int x = a[i].x, y = a[i].y, z = a[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++){int x, y, z;cin >> x >> y >> z;a[i].x = x, a[i].y = y, a[i].z = z;}cout << n - 1 << " ";for (int i = 1; i <= n; i++)f[i] = i;sort(a + 1, a + 1 + m, cmp);kk();cout << ret << endl;
}

P2573 [SCOI2012] 滑雪 - 洛谷

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;typedef long long LL;const int N = 1e5 + 10;
const int M = 2e6 + 10;//考虑两重变typedef pair<int, int> PII;//可以到的点，到该点的距离int n, m;//n个景点，m条边
int h[N];//每个景点的高度vector<PII> dp[N];//记录该点可以去的所有的点+到的距离bool st[N];
LL cnt;//记录有多少个景点被访问了
int pos;//记录有多少条边struct node
{int x, y, z;
}a[M];//记录边的数据int f[N];//并查集void dfs(int u)//找所有可以到达的边
{cnt++;st[u] = true;for (auto& s : dp[u])//遍历该点可以到达的每一条边，并且进行记录{int x = s.first, y = s.second;++pos;//多一条边a[pos].x = u, a[pos].y = x, a[pos].z = y;if (!st[x])//没有被访问过{dfs(x);}}
}
bool cmp(node& x, node& y)//从该点到宁一个点的高的优先，其次是距离
{int x1 = x.x, y1 = x.y, z1 = x.z;int x2 = y.x, y2 = y.y, z2 = y.z;if (h[y1] != h[y2])return h[y1] > h[y2];return z1 < z2;
}int find(int x)
{return f[x] == x ? x : f[x] = find(f[x]);
}LL ret;
void kk()
{sort(a + 1, a + 1 + pos, cmp);for (int i = 1; i <= n; i++)f[i] = i;for (int i = 1; i <= pos; i++){int x = a[i].x, y = a[i].y, z = a[i].z;int fx = find(x);int fy = find(y);if (fx != fy){ret += z;f[fx] = fy;}}}int main()
{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])dp[x].push_back({ y,z });if (h[y] >= h[x])dp[y].push_back({ x,z });//如果是 == 的话，那么两边的都要记录}dfs(1);kk();cout << cnt << " "<<ret << endl;
}

有向图：

由于克鲁斯卡尔算法要把所有的边进行排序没所以我们要创建一个起点,终点，边的结构体

题目没有明确给出那就自己创建。

dfs:把所有的路径都找到。（遍历到一条边就加入路径）
用胶囊把所有可以到的点统计到。->生成最小生成树。

最小生成树：利用dfs找到的路径据生成最小生成树
距离最短->所有距离的总和。--->最小生成树。

选边的时候，优先去往高的位置的边，其次才是距离