Aczy156

Algorithm14.2 最小生成树

[TOC]

最小生成树

几种数据给出形式以及对应的解决方案

1、点a 点b 边ab权值 => 邻接表vector来存 => 优先kruskal

2、一个矩阵 => 邻接矩阵来存【适合存点少线多的，也就是稠密图，如果稀疏的话，空间就爆炸了】 => 优先prim（当然也可以手动提取，但是这样提取会很麻烦，因为边很多，有多少点就要考虑点个数平方个的边）

两种解决方案的大致思路：

1、kruskal克鲁斯卡尔：以边为核心，每次提取权值最小的边，判断是否要这个边的依据就是看这个边的两个端点是否已经在同一个树中

2、prim普里姆：以点为核心，每次拓展 树点集 和 外部点 之间的最小值，从而把外部点拉入到树点集中去

https://www.luogu.com.cn/problem/P3366

模版 - Prim解法 – 邻接矩阵

#include <iostream>
using namespace std;
#define maxn 5005
int n, m, dis[maxn], vis[maxn], mp[maxn][maxn], tem, v, ta, tb, tc, sum;
const int INF = 0x3f3f3f;

void dijkstra(){
    for (int i = 1; i <= n; ++i) dis[i] = mp[1][i];
    for (int i = 2; i <= n; ++i) {
        tem = INF; v = 1;vis[1] = 1;
        for (int j = 2; j <= n; ++j) if (!vis[j] && tem > dis[j]) tem = dis[v=j];
        vis[v] = 1;sum += tem;
        for (int j = 2; j <= n; ++j) if (!vis[j] && dis[j] > mp[v][j]) dis[j] = mp[v][j];
    }
    printf("%d\n", sum);
}

int main() {
    scanf("%d%d", &n, &m);
    // init
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (i == j) mp[i][j] = 0;
            else mp[i][j] = INF;
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &ta, &tb, &tc);
        mp[ta][tb] = mp[tb][ta] = tc;
    }
    dijkstra();
    return 0;
}

模版 - Prim解法 – 邻接表

模版 - kruskal解法

核心思想：边权排序+并查集对点进行分类

https://www.luogu.com.cn/problem/P1396

https://www.luogu.com.cn/problem/P1195 【和上面的区别就是，在判定跳出的时候，要判断当前联通起来的个数，个数等于约定的就推出，不等于约定的就继续往后遍历边即可】

1、两个初始化，边权排序初始化+点集父节点初始化：

边权排序

struct node{
  int from, to, cost;
  bool operator < (const node n) const{return cost < n.cost;}
}edge[maxedge];
sort(edge+1, edge+1+n);

点集父节点初始化

int fa[maxpoint];
for (int i = 1; i <= n; ++i) fa[i] = i;

2、利用并查集对点集进行归类、合并，然后最后跳出的条件是【起终点的fa是一个=>输出结果 // 合并索引idx已经合并完了=>输出无法到达】

// 并查集模版，findfa路径压缩+merge操作
int findfa(int x) {return fa[x]==x? x:fa[x]=findfa(fa[x]);}
void merge(int x, int y) {if (findfa(x) != findfa(y)) fa[findfa(x)] = findfa(y);}

完整AC代码：

#include <iostream>
using namespace std;
#define maxpoint 10010
#define maxedge 20010
int n, m, s, t, fa[maxpoint];
struct node{
    int from, to, cost;
    bool operator < (const node n) const {return cost < n.cost;}
}edge[maxedge];
#include <algorithm>

int findfa(int x) {return fa[x] == x? x:fa[x]=findfa(fa[x]);}

void merge(int x, int y) {if (findfa(x) != findfa(y)) fa[findfa(x)] = findfa(y);}

void kruskal(){
    int idx = 0;
    for (int i = 1; i <= m && idx <= n-1; ++i) {
        if (findfa(edge[i].from) != findfa(edge[i].to)) {merge(edge[i].from, edge[i].to);idx++;}
        if (findfa(s) == findfa(t)) {printf("%d\n", edge[i].cost);break;}
    }
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; ++i) scanf("%d%d%d", &edge[i].from, &edge[i].to, &edge[i].cost);
    // init point and edge
    sort(edge+1, edge+1+m);
    for (int i = 1; i <= n; ++i) fa[i] = i;
    // kruskal
    kruskal();
    return 0;
}

Prim VS kruskal

https://www.luogu.com.cn/problem/P1194

给出一个邻接矩阵，然后根据邻接矩阵求最小生成树。【数据读入的时候需要一点数据预处理的操作】

1、区分prim和kruskal的思路，prim是遍历点=>把附近的最小代价找到然后去更新其他的点；kruskal是遍历边=>直接把所有的边先预排列一下，然后直接从上往下选取代价最小的边即可。

2、区分prim和kruskal的数据结构：

  • prim维护dis[node_number] vis[node_number] mp[node_number][node_number] 或者 vector<node> v; struct node{int to, cost;}
  • kruskal维护结构体数组，struct node{int from, to, cost} edge[edge_number];来描述边；fa[node_number]

kruskal解法

#include <iostream>
using namespace std;
#define maxpoint 505
#define maxedge 250010
int a, b, fa[maxpoint], t, edge_idx;
struct node {
    int from, to, cost;
    bool operator < (const node n) const {return cost < n.cost;}
}edge[maxedge];
#include <algorithm>

int findfa(int x) {return fa[x]==x?x:fa[x]=findfa(fa[x]);}

void merge(int x, int y) { if (findfa(x) != findfa(y)) fa[findfa(x)] = findfa(y);}

void kruskal(){
    int idx = 0, ans = 0;
    for (int i = 1; i <= edge_idx && idx <= b-1; ++i) {
        if (findfa(edge[i].from) != findfa(edge[i].to)) {
            merge(edge[i].from, edge[i].to);
            ans += min(edge[i].cost, a);
            idx++;
        }
    }
    printf("%d\n", a+ans);
}

int main() {
    scanf("%d%d", &a, &b);
    for (int i = 1; i <= b; ++i) {
        for (int j = 1; j <= b; ++j) {
            scanf("%d", &t);
            if (i <= j && t != 0) {edge[++edge_idx].from = i;edge[edge_idx].to = j;edge[edge_idx].cost = t;}
        }
    }
    sort(edge+1, edge+1+edge_idx);
    for (int i = 1; i <= b; ++i) fa[i] = i;
    kruskal();
    return 0;
}

prim解法

#include <iostream>
using namespace std;
#define maxn 505
#define INF 0x3f3f3f
int a, b, mp[maxn][maxn], dis[maxn], v, vis[maxn], tem=INF;

void prim() {
    int ans = a;
    // init dis[] and set 1 as first point
    for (int i = 1; i <= b; ++i) dis[i] = mp[1][i];
    vis[1] = 1;v = 1;
    for (int i = 1; i <= b; ++i) {
        tem = INF;
        for (int j = 2; j <= b; ++j) if (!vis[j] && tem > dis[j])tem = dis[v=j];
        if (tem == INF) break;
        vis[v] = 1;ans += tem;
        for (int j = 2; j <= b; ++j) if (!vis[j] && dis[j] > mp[v][j]) dis[j] = mp[v][j];
    }
    printf("%d\n", ans);
}

int main() {
    scanf("%d%d", &a, &b);
    for (int i = 1; i <= b; ++i)
        for (int j = 1; j <= b; ++j){
            scanf("%d", &mp[i][j]);
            if (!mp[i][j] || mp[i][j] > a) mp[i][j] = a;
        }
    prim();
    return 0;
}

https://www.luogu.com.cn/problem/P2872

1、两种数据预处理方式：

  • 枚举边，添加到结构体数组中 => 跑kruskal。
  • 遍历获取临界矩阵 => 跑prim。

2、隐形条件【所有的MST也都满足的条件】：不成环=>必存在连线数=点数-1

通过声明一个idx，每当增添了一条边之后，idx++，并且在控制循环的位置添加该约束，idx<=n-1

#include <iostream>
using namespace std;
#define maxpoint 1010
#define maxedge 1000010
int n, m, x[maxpoint], y[maxpoint], ta, tb, fa[maxpoint], edge_idx;
struct node{
    int from, to;
    double cost;
    bool operator < (const node n) const {return cost < n.cost;}
}edge[maxedge];
#include <algorithm>
#include <cmath>

double cal(int i, int j) {return sqrt(pow(x[i]-x[j], 2)+pow(y[i]-y[j], 2));}

int findfa(int x) {return fa[x]==x?x:fa[x]=findfa(fa[x]);}

void merge(int x, int y) { if (findfa(x) != findfa(y)) fa[findfa(x)] = findfa(y);}

void kruskal() {
    int idx = 0;
    double ans = 0;
    for (int i = 1; i <= edge_idx && idx <= n-1; ++i) {
        if (findfa(edge[i].from) != findfa(edge[i].to)) {
            merge(edge[i].from, edge[i].to);
            ans += edge[i].cost;
            idx++;
        }
    }
    printf("%.2lf\n", ans);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d%d", &x[i], &y[i]);
    for (int i = 1; i <= n; ++i) {
        for (int j = i+1; j <= n; ++j) {
            edge[++edge_idx].from = i;
            edge[edge_idx].to = j;
            edge[edge_idx].cost = cal(i, j);
        }
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &ta, &tb);
        edge[++edge_idx].from = ta;
        edge[edge_idx].to = tb;
        edge[edge_idx].cost = 0.0;
    }
    // init
    for (int i = 1; i <= n; ++i) fa[i] = i;
    sort(edge+1, edge+1+edge_idx);
    kruskal();
    return 0;
}
Posted on Feb 1, 2021