最小生成树

Prim

与dijkstra算法基本思想相同，唯一不同的是dis表示的不同，在dijkstra中，dis[i]表示i点到起点的最短距离，在Prim中，dis[i]表示i点到已经维护好的树的最短距离。

复杂度$O(n^2+m)$

朴素算法：

struct Node {
    int y, v;
    Node(int  _y, int _v) { y = _y, v = _v; }
};
vector<Node>edge[1010];
int n, m, dis[1010];
bool b[1010];
int Prim() {
    memset(b, false, sizeof(b));
    memset(dis, 127, sizeof(dis));
    dis[1] = 0;//任意设一个起点开始找最短路
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int x = -1;
        for (int j = 1; j <= n; j++) {
            if (!b[j] && dis[j] < 1 << 30) {
                if (x == -1 || dis[j] < dis[x])
                    x = j;
            }
        }
        b[x] = true;
        ans += dis[x];
        for (auto j : edge[x]) {
            dis[j.y] = min(dis[j.y], j.v);
        }
    }
    return ans;
}
void solve() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        edge[x].push_back({ y,z });
        edge[y].push_back({ x,z });
    }
    int ans=Prim();
    printf("%d\n", ans);
}

Prim优化:

通过优先队列(priority_queue)来优化，可以将时间复杂度优化至$O((n+m)logn)$

注意当图中的边特别满的时候，该算法的可能比朴素算法更慢

const int MAXN = 1e5;
struct Edge { int y, v; };
vector<Edge> edge[MAXN * 2];
int n, m;
int dis[50010];
bool b[500010];
int Prim() {
    for (int i = 1; i <= n; i++) dis[i] = INF;
    memset(b, false, sizeof(b));
    dis[1] = 0;//任意确定一个起始点
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
    q.push(make_pair(0, 1));
    int ans = 0;
    while (!q.empty()) {
        pair<int, int> p = q.top(); q.pop();
        int v = p.second;
        if (dis[v] < p.first||b[v]) continue; //此时不满足
        ans += p.first;
        b[v] = true;
        //松弛
        for (int i = 0; i < edge[v].size(); i++) {
            Edge e = edge[v][i];
            if (dis[e.y] > e.v) {
                dis[e.y] = e.v;
                q.push(make_pair(dis[e.y], e.y));
            }
        }
    }
    return ans;
}
void solve() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x, y, v;
        scanf("%d%d%d", &x, &y, &v);
        edge[x].push_back({ y,v });
        edge[y].push_back({ x,v });
    }
    int ans = Prim();
    printf("%d\n", ans);
}

Kruskal

Prim算法每次加点，而Kruskal算法则是通过每次加边来实现

时间复杂度为$O(mlogn)$

struct Node {
    int x, y, v;
    bool operator<(const Node& A) const {
        return v < A.v;
    }
}a[M];
int n, m, pre[N];
void init(int n) {
    for (int i = 1; i <= n; i++) pre[i] = i;
}
int find(int x) {
    if (x != pre[x]) return pre[x]=find(pre[x]);//节省时间
    return x;
}
​
int Kruskal() {
    init(n);
    sort(a + 1, a + m + 1);
    int ans = 0, cnt = n;
    for (int i = 1; i <= m; i++) {
        int x = find(a[i].x), y = find(a[i].y);
        if (x != y) {
            pre[x] = y;
            ans += a[i].v;
            --cnt;
        }
        if (cnt == 1) break;
    }
    if (cnt != 1) return -1;
    else return ans;
}