最小生成树Prim

该算法的基本思想是从一个结点开始，不断加点.每次要选择距离最小的一个结点，以及用新的边更新其他结点的距离。

从任意一个结点开始，将结点分成两类：已加入的，未加入的。
每次从未加入的结点中，找一个与已加入的结点之间边权最小值最小的结点
然后将这个结点加入，并连上那条边权最小的边。
更新所有点到最小生成树的最小边距。
重复 n-1 次即可。

memset(f, 10000000000, sizeof(f));
int dis[N];
for (int i = 1; i <= n; i++)
{
    if (f[i][star])
        dis[i] = f[i][star]; // 每个点到最小生成树的最小边距（没有联系dis[i]就为无穷大
}
dis[star]=0;
int ans = 0;
vis[star] = 1;
for (int i = 1; i < n; i++)
{
    int k = 0;
    int MIN = inf;
    for (int j = 1; j <= n; j++) // 找到最小的边
    {
        if (!vis[j] && (MIN < dis[j])) // 不在生成树中且有联系的最小边
        {
            k = j;
            MIN = dis[j];
        }
    }
    ans += dis[k];
    vis[k] = 1;                  // 记录已在最小生成树中
    for (int j = 1; j <= n; j++) // 更新所有点到最小生成树的最小距离
    {
        if (f[j][k] < dis[j])
            dis[j] = f[j][k];
    }
}

这是大体上的思路实际上可以用优先队列优化