分析

克鲁斯卡尔算法

• 算法思想：将所有边按照边权最小到大排序，依次枚举所有的边，如果边的两个端点已经在同一个集合中（可连通），就continue，否则合并边的两个端点（将边权加入到答案中），直到有n-1条边参与合并为止。

• 最后如何判断这个生成的子图是不是树？--->> 判断边的数量是否为n-1

• 代码

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string>
#include<string.h>
#include<algorithm>
#include <vector>

using namespace std;
#define ll long long
#define sc(x) scanf("%d",&x)
#define scc(x, y) scanf("%d%d",&x,&y)
#define p(x) printf("%d\n",x)
#define m(x, y) (x+y)>>1
#define l(x) x<<1
#define r(x) x<<1|1
const int maxn = 1e5 + 6;
int fa[maxn];
int n;

struct Edge {
    int from, to, cost;

    bool operator<(const Edge &p) const {
        return cost < p.cost;
    }
} edge[maxn];


//找到x的掌门人
int find(int x) {
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);//路径压缩
}

//合并x和y所在的门派
void unite(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) return;
    fa[fx] = fy;
}

//查看x和y的门派是否相同
bool check(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) return true;
    return false;
}

int main() {
    int m, ans, cnt;
    while (~sc(n) && n) {
        sc(m);
        //初始化
        for (int i = 1; i <= n; i++) fa[i] = i;
        ans = 0, cnt = 0;//ans为路程总和，cnt为连接的边的数量
        //读入边
        for (int i = 1; i <= m; i++) scanf("%d%d%d", &edge[i].from, &edge[i].to, &edge[i].cost);
        //对边的权值排序
        sort(edge + 1, edge + m + 1);
        
        for (int i = 1; i <= m; i++) {
            //若两点不在同一条线
            if (!check(edge[i].from, edge[i].to)) {
                ans += edge[i].cost;
                cnt++;
                unite(edge[i].from, edge[i].to);//合并
            }
        }
        //检验，打印cost之和
        if (cnt == n - 1) p(ans);
    }
    return 0;
}

题目

用多组数据，用空行隔开，每组数据第一行有两个数，n个点和m个边，接下来有m行，from，to，cost，最后以0结尾。

• 输入示例

1 0

2 3
1 2 37
2 1 17
1 2 68

3 7
1 2 19
2 3 11
3 1 7
1 3 5
2 3 89
3 1 91
1 2 32

5 7
1 2 5
2 3 7
2 4 8
4 5 11
3 5 10
1 5 6
4 2 12

0

• 输出示例

0
17
16
26

Prim算法

• 思想：
  1.因为生成树每个点都需要连接，所以可以从任意一个顶点开始构造生成树，我们使用1号顶点。首先将1号加入生成树中。
  2.用dis数组记录各点到生成树的距离
  3.从数组dis中选出离生成树最近的顶点j，再以j为中间点，更新生成树到每一个非树顶点的距离
  4.重复第3步，直到生成树中有n个顶点为止。
• 未优化的代码（O（n^2））

int main() {
    int n, m, s, e, cost, min, i, j, k;
    int a[50][50], dis[50], book[100] = {0};
    int count = 0, sum = 0;

    scc(n, m);
    //初始化
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (i == j) a[i][j] = 0;
            else a[i][j] = oo;
        }
    }

    //读入边
    for (i = 1; i <= m; i++) {
        sccc(s, e, cost);
        a[s][e] = cost;
        a[e][s] = cost;
    }

    //初始化dis数组，这里是1号顶点到各个顶点的初始距离
    for (i = 1; i <= n; i++)
        dis[i] = a[1][i];

    //Prime核心部分
    //将1号顶点加入生成树
    book[1] = 1;
    count++;
    while (count < n) {
        min = oo;
        for (i = 1; i <= n; i++) {
            if (book[i] == 0 && dis[i] < min) {
                min = dis[i];
                j = i;
            }
        }
        book[j] = 1;
        count++;
        sum += dis[j];

        //扫描当前顶点所有的边，再以j为中间点，
        //更新生成树到每一个非树顶点的距离
        for (k = 1; k <= n; k++) {
            if (book[k] == 0 && dis[k] > a[j][k])
                dis[k] = a[j][k];
        }
    }
    p(sum);
    return 0;

}

• 使用堆优化(O(MlogN))

#include<stdio.h>
#include <iostream>
#include<cmath>
#include <cctype>
#include <cstdlib>
#include<cstring>
#include<algorithm>
#include <vector>
#include<queue>

using namespace std;
#define ll long long
#define il inline
#define oo (2147000000)
#define sc(x) scanf("%d",&x)
#define scc(x, y) scanf("%d%d",&x,&y)
#define sccc(x, y, z) scanf("%d%d%d",&x,&y,&z)
#define p(x) printf("%d\n",x)
#define m(x, y) ((x+y)>>1)
#define l(x) (x<<1)
#define r(x) (x<<1|1)
const int maxn = 1e5 + 6;

int dis[100], book[100];
int h[1000], pos[1000], size;
//h用来保存堆(h[i]表示顶点编号)，pos用来储存顶点在堆中的位置，size表示堆的大小

void swap(int x, int y) {
    int t;
    t = h[x];
    h[x] = h[y];
    h[y] = t;

    //同步更新pos
    t = pos[h[x]];
    pos[h[x]] = pos[h[y]];
    pos[h[y]] = t;
}

//向下调整
void siftdown(int i) {   //传入一个向下调整的节点编号
    int t, flag = 0;    //flag标记是否需要继续向下调整

    while (i * 2 <= size && flag == 0) {
        //判断它和左儿子的关系，并用t记录值较小的节点编号
        if (dis[h[i]] > dis[h[i * 2]]) t = i * 2;
        else t = i;

        //和右儿子
        if (i * 2 + 1 <= size) {
            if (dis[h[t]] > dis[h[i * 2 + 1]])
                t = i * 2 + 1;
        }
        //如果不是自己
        if (t != i) {
            swap(t, i);
            i = t;
        } else flag = 1;
    }
    return;
}

//传入一个需要向上调整的顶点编号i
void siftup(int i) {
    int flag = 0;
    if (i == 1) return;

    while (i != 1 && flag == 0) {
        //判断是否比父节点小
        if (dis[h[i]] < dis[h[i / 2]])
            swap(i, i / 2);
        else
            flag = 1;
        i = i / 2;
    }
}


//删除最小的元素
int pop() {
    int t = h[1];
    h[1] = h[size];
    pos[h[1]] = 1;
    size--;
    siftdown(1);
    return t;
}

int main() {
    //u、v、w和next的数组大小要根据实际情况来设置，此图是无向图，要比2*m的最大值大1
    //first要比n的最大值大1，要比2*m的最大值大1
    int n, m, i, j, k, u[maxn], v[maxn], w[maxn], first[maxn], next[1000];
    int count = 0, sum = 0;

    scc(n, m);

    //读入边，使用邻接表储存
    for (i = 1; i <= m; i++) {
        sccc(u[i], v[i], w[i]);
    }

    //这里是无向图，所以需要将所有的边再反向储存一次
    for (i = m + 1; i <= 2 * m; i++) {
        u[i] = v[i - m];
        v[i] = u[i - m];
        w[i] = w[i - m];
    }

    //开始使用邻接表储存边
    for (i = 1; i <= n; i++) first[i] = -1;

    for (i = 1; i <= 2 * m; i++) {
        next[i] = first[u[i]];
        first[u[i]] = i;
    }

    //Prime核心部分
    //将1号顶点加入生成树
    book[1] = 1;
    count++;

    //初始化dis数组，这里是1号顶点到各个顶点的初始距离
    for (i = 2; i <= n; i++) dis[i] = oo;
    k = first[1];
    while (k != -1) {
        dis[v[k]] = w[k];
        k = next[k];
    }

    //初始化堆
    size = n;//此处必须使用size来备份n,不然pop函数会n--,导致n变化
    for (i = 1; i <= size; i++) {
        h[i] = i;
        pos[i] = i;
    }
    for (i = size / 2; i >= 1; i--) {
        siftdown(i);
    }
    pop();


    while (count < n) {
        j = pop();
        book[j] = 1;
        count++;
        sum += dis[j];

        //扫描当前顶点所有的边，再以j为中间点，
        //更新生成树到每一个非树顶点的距离
        k = first[j];
        while (k != -1) {
            if (book[v[k]] == 0 && dis[v[k]] > w[k]) {
                dis[v[k]] = w[k];
                siftup(pos[v[k]]);
                //pos储存的是顶点v[k]在堆中的位置
            }
            k = next[k];
        }
    }
    p(sum);
    return 0;

}