最小生成树之prim

现在来补发之前c++作业的总结，不得不说，那次作业确实有点难顶，涉及到复杂的算法，好在洛谷社区有模板套，现在来削微总结下算法，尽管现在能理解算法背后的原理，但还是写不出算法，趁现在还记得这件事先记录下，日后经验丰富后再来回顾

代码如下

#include <bits/stdc++.h>
using namespace std;
double book[100], dis[100], MAX = 99999, maps[100][100];
vector<double> length(0);
// vector<double> ttt(0);
class point
{
private:
    double x, y;

public:
    double getx() const { return x; }
    double gety() const { return y; }
    void set()
    {
        cin >> x >> y;
    }
};
double calc(point p1, point p2)
{
    double l1, l2;
    l1 = (p1.getx() - p2.getx()) * (p1.getx() - p2.getx());
    l2 = (p1.gety() - p2.gety()) * (p1.gety() - p2.gety());
    return sqrt(l1 + l2);
}

int main()
{
    int n = 5, m = 10, i, j;
    int min, minIndex;
    double sum = 0;
    vector<point> pp(6);
    for (int i = 1; i <= 5; i++)
    {
        pp[i].set();
    }
    // 对maps初始化，除了自己到自己距离是0，其他都是边界值
    for (i = 1; i <= n;i++)
    {
        for (j = 1; j <= n;j++)
        {
            if(i != j)
                maps[i][j] = MAX;
            else
                maps[i][j] = 0;
        }
    }
    // 输入数据，输入无向图
    for (int i = 1; i < 6;i++)
    {
        for (int j = i + 1; j < 6;j++)
        {
            double temp = calc(pp[i], pp[j]);
            length.push_back(temp);
            maps[i][j] = temp;
            maps[j][i] = temp;
        }
    }
    // 初始化距离数组，默认把离1最近的找出来储存起来
    for (i = 1; i <= n; i++)
        dis[i] = maps[1][i];
    book[1] = 1;
    for (i = 1; i <= n - 1; i++)
    {
        min = MAX;
    // 对最小值复制，寻找离树最近的点
        for (j = 1; j <= n; j++)
        {
            if (book[j] == 0 && dis[j] < min)
            {
                min = dis[j];
                minIndex = j;
            }
        }
        // 标记这个点被访问过
        book[minIndex] = 1;
        sum += dis[minIndex];
        for (j = 1; j <= n; j++)
        {
        // 如果这个点没被访问过，如果距离更近就更新
            if (book[j] == 0 && maps[minIndex][j] < dis[j])
                dis[j] = maps[minIndex][j];
        }
    }
    cout.setf(ios::fixed);
    cout << setprecision(6) << sum << endl;
    cout << endl;
    // 输出最小生成树
}

快速理解原理：2分钟搞懂最小生成树prim算法_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili

题解模板：P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) (有很多模板，选择适合自己，能看懂的为上策)