2025-02-09最小生成树的扩展应用

最小生成树的扩展应用

主要内容

最小生成树相关知识点

  • 定义与性质
    • 最小生成树是指在一个加权连通图里，找到一棵生成树，其所有边的权值之和最小。
    • 最小生成树的边数等于顶点数减1。
    • 最小生成树不唯一，但其边权之和唯一。
  • Kruskal算法
    • 基本思想：按照边权从小到大的顺序选择边，每次选择的边不会与已选择的边构成环，直到选择n-1条边为止。
    • 实现步骤：
      1. 对所有边按照权值从小到大排序。
      2. 初始化并查集，每个顶点自成一个集合。
      3. 遍历排序后的边，对于每条边，如果它的两个端点属于不同的集合，则将这条边加入最小生成树，并合并这两个集合。
      4. 重复上一步，直到选择n-1条边或所有顶点都在同一个集合中。
    • 适用场景：适用于边数较多的稀疏图。
    • 时间复杂度：主要取决于排序的复杂度，为O(ElogE)，其中E为边数。
  • 并查集
    • 基本操作
      • 查找：确定元素所属集合的代表元素（根节点），路径压缩可以优化查找效率，使每次查找的时间复杂度接近O(1)。
      • 合并：将两个元素所在的集合合并为一个集合，按秩合并可以避免树过高，保证操作效率。
    • 在最小生成树中的作用：用于判断两个顶点是否在同一棵树（集合）中，从而判断加入一条边是否会形成环。
    • 维护集合大小：每个集合的大小的可维护的。

例题中的扩展应用知识点

  • 添加虚拟节点
    • 在“新的开始”例题中，引入“超级发电站”作为虚拟节点，将建立发电站的问题转化为从该虚拟节点引出线路的问题，从而将问题转化为最小生成树问题。这种方法可以将一些特殊约束条件转化为图论模型中的常规元素，方便利用最小生成树算法求解。
  • 结合其他约束条件
    • 北极通讯网络：考虑了卫星电话数量的限制，将部分边用卫星通话代替，从而优化了最小生成树的构建过程。这体现了在实际问题中，最小生成树问题可能需要结合其他条件进行调整和优化，以满足特定需求。
    • 秘密的牛奶运输：涉及到次小生成树的求解，包括严格次小生成树和非严格次小生成树的概念及求解方法。这说明在一些问题中，除了最小生成树本身，还需要考虑与最小生成树相近的其他生成树，以应对不同的问题要求。
  • 维护额外信息
    • 走廊泼水节：在构建最小生成树的过程中，需要维护并查集的大小，通过size数组记录每个集合的大小，以便在计算结果时考虑集合大小对最终答案的影响。这表明在某些情况下，除了基本的最小生成树结构，还需要额外维护一些信息，以满足问题的特殊要求。
  • 路径上最大边的维护
    • 在“秘密的牛奶运输”中，通过DFS或LCA等方法维护最小生成树中两点路径上的最大边权值，以便在求次小生成树时进行权值的更新和比较。这体现了在一些复杂问题中，需要对最小生成树的结构进行更深入的分析和处理，以获取更详细的信息用于进一步的计算。

例题

新的开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// http://ybt.ssoier.cn:8088/problem_show.php?pid=1488
/*
 * 假想在某处建立发电站等于从“超级发电站”引出一条线路到该点，路径花费为发电站造价
 * 把所有假想路径也加进去，就变成了典型的最小生成树问题！
 * 这里至少要有一个地方要建发电站，所以“超级发电站”一定要包括在内
*/

#include<bits/stdc++.h>
using namespace std;

const int N = 310, M=N*N+N+10;
struct Edge{
    int a, b, w;
    bool operator<(const Edge& t)const{
        return w<t.w;
    }
}e[M];
int p[N];
int n;

int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

void work(){
    cin>>n;

    for(int i=0;i<=n;i++) p[i]=i;

    int cnt=0;
    for(int i=1;i<=n;i++){
        int w;
        cin>>w;
        e[cnt++]={0, i, w};
    }

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            int w;
            cin>>w;
            if(i<j){
                e[cnt++]={i, j, w};
            }
        }  

    sort(e, e+cnt);

    int res=0;
    for(int i=0;i<cnt;i++){
        int a=find(e[i].a), b=find(e[i].b), w=e[i].w;
        if(a!=b){
            res+=w;
            p[a]=b;
        }
    }

    cout<<res<<endl;
}

int main(){
    work();
    return 0;
}

北极通讯网络

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// http://ybt.ssoier.cn:8088/problem_show.php?pid=1487

#include<bits/stdc++.h>
using namespace std;

int n, k;
const int N=510, M=N*N+10;
struct Edge{
    int a, b;
    float w;
    bool operator<(const Edge&t)const{
        return w<t.w;
    }
}e[M];

struct Point{
    float x, y;
}a[N];
float dis(Point& p1, Point& p2){
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

int p[N];

float res[N];
int idx=0;


int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

void work(){
    scanf("%d%d", &n, &k);
    k--;//k个卫星电话可以代替k-1条线路

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

    for(int i=1;i<=n;i++){
        scanf("%f%f", &a[i].x, &a[i].y);
    }

    int cnt=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(i<j){
                e[cnt++]={i, j, dis(a[i], a[j])};
            }
        }

    sort(e, e+cnt);

    for(int i=0;i<cnt;i++){
        int a=find(e[i].a), b=find(e[i].b);
        float w=e[i].w;
        if(a!=b){
            p[a]=b;
            res[idx++]=w;
        }
    }

    if(idx<=k) printf("%.2lf\n", 0.00);
    else printf("%.2lf\n", res[idx-k-1]);//最大的若干条边用卫星通话代替
}

int main(){
    work();
    return 0;
}

走廊泼水节

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// https://www.luogu.com.cn/problem/P10928

/*
 * 从小到大遍历最小生成树的每一条边{a, b, w}，
 * 合并两端点a, b各自所在的联通块，两个联通块各取一点组合连接，考虑最小生成树唯一，边权w+1
 * 减去a, b连接的那条边 
 * 
 * 这里要维护并查集的大小，用size数组，size[i]表示i所在集合大小
*/

#include<bits/stdc++.h>
using namespace std;

const int N=6010;
int n;
struct Edge{
    int a, b, w;
    bool operator<(const Edge&t)const{
        return w<t.w;
    }
}e[N];
int p[N], size[N];

int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

void work(){
    int t;
    cin>>t;

    while(t--){
        cin>>n;

        for(int i=1;i<=n;i++){
            p[i]=i;
            size[i]=1;
        } 

        for(int i=0;i<n-1;i++){
            int a, b, w;
            cin>>a>>b>>w;
            e[i]={a, b, w};
        }

        sort(e, e+n-1);

        int res=0;
        for(int i=0;i<n-1;i++){
            int a=find(e[i].a), b=find(e[i].b), w=e[i].w;
            if(a!=b){
                res+=(size[a]*size[b]-1)*(w+1);
                size[b]+=size[a];//只维护父节点
                p[a]=b;
            }
        }

        cout<<res<<endl;
    }
}

int main(){
    work();
    return 0;
}

秘密的牛奶运输

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
// http://ybt.ssoier.cn:8088/problem_show.php?pid=1490

/*
 * 次小生成树有两种，严格和非严格的，非严格的可以允许权重之和等于最小生成树的
 * 解决次小生成树有两种方法
 * 第一种：求出最小生成树后，枚举删除其一条边，再求剩余图的最小生成树，维护最小权重和，只能解决非严格
 * 
 * 第二种（比较常用）：枚举非最小生成树边添加到最小生成树中，再删除最小生成树的一条边，维护最小权重和
 * 记sum为最小生成树的权重之和，枚举到非树边{a, b, w}，dist[a][b]为最小生成树中a到b路径上最大边
 * new_sum=sum+w-dist[a][b]
 * 注意，在求严格次小生成树时，要确保new_sum严格大于sum，也就是w要严格大于dist[a][b]，才更新最值
 * 有关dist数组的维护，比较好的做法是用lca，这里用粗糙的dfs求出也能勉强通过
*/

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=2010, M=20010;
const ll INF=1e18;

//Kruskal
struct Edge{
    int a, b;
    ll w;
    bool f;
    bool operator<(const Edge&t)const{
        return w<t.w;
    }
}edge[M];
int p[N];

int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

//邻接表
int h[N], e[2*M], ne[2*M], idx;
ll w[2*M];

void add(int a, int b, ll c){
    e[idx]=b, w[idx]=c, ne[idx]=h[a], h[a]=idx++;
}

//维护路径上最大边
ll dist[N][N];
void dfs(int u, int fa, ll maxd, ll d[]){
    d[u]=maxd;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j!=fa){
            dfs(j, u, max(w[i], maxd), d);
        }
    }
}

int n, m;

void work(){
    scanf("%d%d", &n, &m);

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

    for(int i=0;i<m;i++){
        int a, b;
        ll c;
        scanf("%d%d%lld", &a, &b, &c);
        edge[i]={a, b, c, false};
    }

    sort(edge, edge+m);

    ll sum=0;
    memset(h, -1, sizeof h);
    for(int i=0;i<m;i++){
        int a=find(edge[i].a), b=find(edge[i].b);
        ll c=edge[i].w;
        if(a!=b){
            p[a]=b;
            sum+=c;
            add(edge[i].a, edge[i].b, c), add(edge[i].b, edge[i].a, c);
            edge[i].f=true;//标记这条边在最小生成树上
        }
    }

    //计算dist
    for(int i=1;i<=n;i++) dfs(i, -1, 0, dist[i]);

    ll res=INF;
    for(int i=0;i<m;i++){
        if(!edge[i].f){
            int a=edge[i].a, b=edge[i].b;
            ll c=edge[i].w;
            if(c>dist[a][b]) res=min(res, sum+c-dist[a][b]);
        }
    }

    printf("%lld\n", res);
}

int main(){
    work();
    return 0;
}
寒假练题计划 > 提高算法 > 图论 > 最小生成树
#cpp #algorithm #ACwing #MST #Kruskal #Prim #Disjoint-set #DFS #LCA
2025-02-09最小生成树的扩展应用
http://666xz666.github.io/2025/02/09/最小生成树的扩展应用/
作者
666xz666
发布于
2025年2月9日
许可协议