第三章 图论 No.5最小生成树之虚拟源点，完全图与次小生成树

文章目录

      • 虚拟源点：1146. 新的开始
      • 贪心或kruskal性质：1145. 北极通讯网络
      • 最小生成树与完全图：346. 走廊泼水节
      • 次小生成树：1148. 秘密的牛奶运输

虚拟源点：1146. 新的开始

1146. 新的开始 - AcWing题库
image.png

与一般的最小生成树问题不同，本题需要在建立电站的电井之间建立电网，在两个电站之间建立电网需要花费金额，可以看成一条具有权值的边
但是建立电网的前提是：其中一个电井需要建立电站，建立电站也需要费用
已经建立电站的两个电井之间无需建立电网，即一张电网中只需要存在一个建立电站的电井
可以将建立电站也看成具有权值的边，设置虚拟源点，在第i个电井建立电站可以转换成虚拟源点与i点之间的边，权值为建立电站的费用
此时跑个最小生成树即可

为什么不能直接跑最小生成树，再选择某个点建立一个最便宜的电站？只建立一个电站虽然能保证所有电井有电，但是两个电井建立电网的费用可能高于直接建立电站的费用
所以可能会建立多个电站，即最小生成“森林”，设置虚拟选点就是将每个森林连接，即最小生成树，此时需要跑最小生成树的算法即可

// 跑一遍最小生成树，记录其中点的最小值
#include <iostream>
#include <cstring>
using namespace std;

const int N = 310;
int g[N][N], dis[N];
bool st[N];
int n;

int prim()
{
    memset(dis, 0x3f, sizeof(dis));
    int res = 0;
    for (int i = 0; i <= n; ++ i )
    {
        int x = -1;
        for (int j = 0; j <= n; ++ j )
            if (!st[j] && (x == -1 || dis[x] > dis[j])) x = j;
        st[x] = true;
        if (i) res += dis[x];
        for (int y = 0; y <= n; ++ y )
            dis[y] = min(dis[y], g[x][y]);
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i ) 
    {
        scanf("%d", &g[0][i]);
        g[i][0] = g[0][i];
    }
    for (int i = 1; i <= n; ++i )
        for (int j = 1; j <= n; ++ j )
            scanf("%d", &g[i][j]);
            
    printf("%d\n", prim());
    
    return 0;
}

贪心或kruskal性质：1145. 北极通讯网络

1145. 北极通讯网络 - AcWing题库
image.png

三种解法，第一种，一眼想到的就是贪心：
跑个最小生成树，升序记录所有边权
若有k个卫星，选择第k大的边即可，因为k个卫星使得k个村庄可以直接通信
k-1条最大边连接的村庄用卫星，其他用发电设备通信，此时d为最大的边权

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;
const int N = 510, INF = 0x3f3f3f3f;
double g[N][N], res[N];
double dis[N];
PII a[N];
bool st[N];
int n, k;

double get_dis(PII a, PII b)
{
    int x = a.x - b.x, y = a.y - b.y;
    return sqrt(x * x + y * y);
}

double prim()
{
    for (int i = 1; i <= n; ++ i ) dis[i] = INF;
    for (int i = 0; i < n; ++ i )
    {
        int x = -1;
        for (int j = 1; j <= n; ++ j )
            if (!st[j] && (x == -1 || dis[x] > dis[j])) x = j;
        st[x] = true;
        if (i) res[i] = dis[x];
        
        for (int y = 1; y <= n; ++ y )
            dis[y] = min(dis[y], g[x][y]);
    }
    sort(res + 1, res + n);
    return res[n - k]; // 1 ~ n-1 为最小生成树的边权升序排序
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++ i )
        scanf("%d%d", &a[i].x, &a[i].y);
    
    if (k >= n) puts("0.00");
    else
    {
        for (int i = 1; i <= n; ++ i )
            for (int j = i + 1; j <= n; ++ j )
                g[i][j] = g[j][i] = get_dis(a[i], a[j]);
                
        printf("%.2lf\n", prim());
    }
    
    return 0;
}

kurskal的性质：
每次kruskal选择当前最小边更新时，本质是在建立连通块，初始每个点各自为连通块，数量为n，每次更新连通块的数量-1，更新n-1次选择了n-1条边后，连通块的数量为1，此时最小生成树构建完成

转换题意，找到一个最小d值，删除所有大于等于d的边后，剩下的连通块数量不超过k，两个连通块中的村庄用卫星通信通信
利用kruskal的性质，更新t次后， n − t = k n-t = k n−t=k时，表示已经建立了k个连通块，这些连通块中的最大边权为答案

// 跑个最小生成树，升序记录所有边权
// 若有k个卫星，选择第k大的边即可，因为k个卫星使得k个村庄可以直接通信
// k-1个最大边连接的存在用卫星，其他用发电设备通信
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

typedef pair<int, int> PII;
const int N = 510, M = N * N / 2;
int p[N];
PII a[N];
bool st[N];
int n, k, cnt;

struct Edge
{
    int x, y;
    double w;
    bool operator<(const Edge& e)
    {
        return w < e.w;
    }
}edges[M];

double get_dis(PII a, PII b)
{
    int x = a.first - b.first, y = a.second - b.second;
    return sqrt(x * x + y * y);
}

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

double kruskal()
{
    double res;
    int u = 0;
    sort(edges, edges + cnt);
    for (int i = 1; i <= n; ++ i) p[i] = i;
    for (int i = 0; i < cnt; ++ i )
    {
        if (n - u == k) break;
        auto t = edges[i];
        int x = t.x, y = t.y;
        double w = t.w;
        x = find(x), y = find(y);
        if (x != y)
        {
            u ++ ;
            res = w;
            p[x] = y;
        }
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++ i )
        scanf("%d%d", &a[i].first, &a[i].second);
    
    if (k >= n) puts("0.00");
    
    else
    {
        for (int i = 1; i <= n; ++ i )
            for (int j = i + 1; j <= n; ++ j )
                edges[cnt ++ ] = { i, j, get_dis(a[i], a[j])};
                
        printf("%.2lf\n", kruskal());
    }
    
    return 0;
}

debug：Edge中的w要用double存

最小生成树与完全图：346. 走廊泼水节

346. 走廊泼水节 - AcWing题库
image.png

如何合并完全图？开始时图中的每个点各自为一个集合，用集合合并的方式，保证合并后的集合为一个完全图
若集合a有x个点，b有y个点，要使得两集合合并后是个完全图（合并前两集合分别是完全图），就要将属于不同集合的点之间建一条边，总共需要建立xy条边

现在的问题是，将两个集合合并成完全图的边权为多大才能满足题意？
将树的每条边从小到大排序，每次合并当前枚举的边连接的两个集合，保证合并后的集合是一个完全图
由于要保证完全图的最小生成树唯一，所以要保证用来建立完全图的边权大于原生成树的边权

即当前枚举第i条边，这条边连接两个点 x i , y i x_i, y_i xi​,yi​，将 x i , y i x_i, y_i xi​,yi​所属的两个集合合并成完全图，需要在两个集合中的每个点之间建立一条边，并且该边的权值需要大于 w i w_i wi​

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 6010;
struct Edge
{
    int x, y, w;
    bool operator<(const Edge& e) const 
    {
        return w < e.w;
    }
}edges[N];
int p[N], sz[N];

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

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n - 1; ++ i )
            scanf("%d%d%d", &edges[i].x, &edges[i].y, &edges[i].w);
        
        sort(edges, edges + n - 1);
        long long res = 0;
        for (int i = 1; i <= n; ++ i ) p[i] = i, sz[i] = 1;
        for (int i = 0; i < n - 1; ++ i )
        {
            auto t = edges[i];
            int x = find(t.x), y = find(t.y), w = t.w;
            if (x != y)
            {
                int n1 = sz[x], n2 = sz[y];
                p[x] = y;
                sz[y] += sz[x];
                res += (n1 * n2 - 1) * (w + 1);
            }
        }
        printf("%lld\n", res);
    }
    
    return 0;
}

debug：edges忘记了排序

次小生成树：1148. 秘密的牛奶运输

1148. 秘密的牛奶运输 - AcWing题库
image.png

次小生成树：
image.png

先求出最小生成树，删除最小生成树中的一条边
重复n-1次，得到的最小生成树就是次小生成树
注意：只能求出非严格次小生成树，即次小生成树的权值和可能等于最小生成树
时间复杂度 O ( m l n g m + n m ) O(mlngm + nm) O(mlngm+nm)

先求最小生成树，枚举不在树中的边，同时删除最小生成树（构成环）中的最大边，使得最终得到的图仍然是一颗树，次小生成树一定在这些树中

在生成树中任意添加一条边，必定构成环，此时需要在这个环路中删除一条边，使得该图再次成为一颗树，由于要保证权值和最小，所以要删除一条最大边
每次枚举非树边时，需要判断该边权值是否大于环的最大边，若大于则删除环中的最大值，此时能保证次小生成的权值和严格大于最小生成树
不过这种情况有一个特例，若非树边的权值等于最大边，当环中所有边的权值都等于最大边时，不更新次小生成树没有问题。若环中存在边权小于最大边的权值呢？此时可以删除这条次大的边，更新次小生成树。所以只通过判断非树边是否大于最大值将漏掉一些情况，导致少枚举次小生成树，最终导致答案的错误
因此，除了要维护两点间的最大边，还需要维护两点间的次大边，并且次大边需要严格小于最大边

若要生成非严格的次小生成树，只需要修改判断条件，在非树边的权值大于等于环的最大值时更新。多了权值相等的情况，所以删除的最大边可能和非树边权值相等，那么生成的次小生成树权值和就是相同的
image.png

先预处理树中两点间的最大边，从根节点出发做一个dfs，每次都要 O ( n ) O(n) O(n)，时间复杂度是 O ( n 2 ) O(n^2) O(n2)
总的次小生成树的时间复杂度为 O ( m l n g m + n 2 + m ) O(mlngm + n^2 + m) O(mlngm+n2+m)

image.png
由于第二种求次小生成树的方式既可以求最小生成树也能求次小生成树，所以这里实现第二种
用两个二维数组表示最小生成树中任意两点的最大边与次大边

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 510, M = 1e4 + 10;
struct Edge
{
    int x, y, w;
    bool f;
    bool operator<(const Edge& e) const 
    {
        return w < e.w;
    }
}edges[M];

int p[N];
int h[N], e[M], ne[M], w[M], idx;
int dmax1[N][N], dmax2[N][N];
int n, m;

void add(int x, int y, int d)
{
    e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}

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

// 走到x的最大边与次大边
void dfs(int x, int f, int d1, int d2, int xmax1[], int xmax2[])
{
    xmax1[x] = d1, xmax2[x] = d2;
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (y != f)
        {
            int t1 = d1, t2 = d2;
            if (w[i] > t1) t2 = t1, t1 = w[i];
            else if (w[i] < t1 && w[i] > t2) t2 = w[i];
            dfs(y, x, t1, t2, xmax1, xmax2);
        }
    }
}

LL kruskal()
{
    LL sum = 0;
    sort(edges, edges + m);
    for (int i = 1; i <= n; ++ i ) p[i] = i;
    for (int i = 0; i < m; ++ i )
    {
        auto t = edges[i];
        int x = t.x, y = t.y, w = t.w;
        int px = find(t.x), py = find(t.y);
        if (px != py)
        {
            sum += w;
            p[px] = py;
            add(x, y, w), add(y, x, w); // 存储最小生成树
            edges[i].f = true; // 树边
        }
    }
    return sum;
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++ i ) scanf("%d%d%d", &edges[i].x, &edges[i].y, &edges[i].w);
    LL sum = kruskal();
    for (int i = 1; i <= n; ++ i ) dfs(i, -1, -1e9, -1e9, dmax1[i], dmax2[i]);
    LL res = 1e19;
    for (int i = 0; i < m; ++ i )
    {
        if (!edges[i].f)
        {
            int x = edges[i].x, y = edges[i].y, w = edges[i].w;
            if (w > dmax1[x][y]) res = min(res, sum - dmax1[x][y] + w);
            else if (w > dmax2[x][y]) res = min(res, sum - dmax2[x][y] + w);
        }
    }
    printf("%lld\n", res);
    return 0;
}

debug：构建最小生成树的同时，用邻接表存储最小生成树

auto t = edges[i];
int x = find(t.x), y = find(t.y), w = t.w;
if (x != y)
{
	sum += w;
	p[x] = y;
	add(x, y, w), add(y, x, w); // 存储最小生成树
	edges[i].f = true; // 树边
}

若这样写，构建的最小生成树是正确的，但是存储的最小生成树确实不正确的
因为x和y是边的两点所属的集合，不一定是边的两点，所以此时add无法正确保存最小生成树

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/67189.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

（MVC）SpringBoot+Mybatis+Mapper.xml

（MVC）SpringBoot+Mybatis+Mapper.xml

前言&#xff1a;本篇博客主要对MVC架构、Mybatis工程加深下理解&#xff0c;前面写过一篇博客&#xff1a;SprintBoothtml/css/jsmybatis的demo&#xff0c;里面涉及到了Mybatis的应用&#xff0c;此篇博客主要介绍一种将sql语句写到了配置文件里的方法&#xff0c;即Mybatis里…
阅读更多...
将大容量机械硬盘克隆到固态硬盘的简单方法！

将大容量机械硬盘克隆到固态硬盘的简单方法！

可以大容量机械硬盘克隆到固态硬盘吗&#xff1f; 随着硬盘使用时间增长&#xff0c;电脑的性能可能会下降。为了追求更快的读写速度&#xff0c;不少用户将目光投向了固态硬盘。 ​众所周知&#xff0c;固态硬盘的读写速度和启动速度比机械硬盘快。用固态硬盘替…
阅读更多...
计算机网络 数据链路层 媒体接入控制

计算机网络 数据链路层 媒体接入控制

阅读更多...
k8s --pod详解

k8s --pod详解

目录 一、Pod基础概念 1、pod简介 2、在Kubrenetes集群中Pod有如下两种使用方式 3、pause容器使得Pod中的所有容器可以共享两种资源&#xff1a;网络和存储。 &#xff08;1&#xff09;网络 &#xff08;2&#xff09;存储 4、kubernetes中的pause容器主要为每个容器提供…
阅读更多...
4.2、Flink任务怎样读取文件中的数据

4.2、Flink任务怎样读取文件中的数据

目录 1、前言 2、readTextFile&#xff08;已过时&#xff0c;不推荐使用&#xff09; 3、readFile&#xff08;已过时&#xff0c;不推荐使用&#xff09; 4、fromSource(FileSource) 推荐使用 1、前言 思考: 读取文件时可以设置哪些规则呢&#xff1f; 1. 文件的格式(tx…
阅读更多...
Babylon.js着色器简明简称【Shader】

Babylon.js着色器简明简称【Shader】

推荐&#xff1a;用 NSDT设计器 快速搭建可编程3D场景 为了生成 BabylonJS 场景&#xff0c;需要用 Javascript 编写代码&#xff0c;BabylonJS 引擎会处理该代码并将结果显示在屏幕上。 场景可以通过改变网格、灯光或摄像机位置来改变。 为了及时显示可能的变化&#xff0c;屏…
阅读更多...
kubernetes中最小组件——Pod

kubernetes中最小组件——Pod

目录 一、Pod简介 二、Pod的使用方式 三、Pause——Pod中底层基础容器 四、为什么kubernetes这样设计Pod 五、Pod的分类 1.自主式Pod 2.控制器管理的Pod 3.静态Pod 六、Pod容器的分类 1. 基础容器&#xff08;infrastructure container&#xff09; 2. 初始化容器&am…
阅读更多...
MySQL DAL单表练习一（学生表）

MySQL DAL单表练习一（学生表）

目录 步骤&#xff1a; 1、创建学生表 2、插入数据 1&#xff09;查询表中所有学生的信息 2&#xff09;查询表中所有学生的姓名和英语成绩 3&#xff09; 过滤表中的重复数据 4&#xff09; 统计每个学生的总分 5&#xff09; 所有学生总分上加上10 6&#xff09; 使…
阅读更多...
微信个人小程序申请 (AppID 和 AppSecret)

微信个人小程序申请 (AppID 和 AppSecret)

1. 登录微信公众平台 https://mp.weixin.qq.com/cgi-bin/loginpage?url%2Fcgi-bin%2Fhome%3Ft%3Dhome%2Findex%26lang%3Dzh_CN%26token%3D47421820 2. 右上角立即注册 3. 注册类型选择小程序 4. 账号信息 5. 邮箱激活 6. 小程序发布流程 7. 小程序信息 (前往填写) 8. 获取小程…
阅读更多...
【Axure高保真原型】JS版日期区间下拉选择器

【Axure高保真原型】JS版日期区间下拉选择器

今天和大家分享JS版日期区间下拉选择器的原型模板&#xff0c;该模板通过调用浏览器的下拉列表&#xff0c;所以可以获取真实的日历效果&#xff0c;具体包括哪一年二月份有29天&#xff0c;几号对应星期几&#xff0c;都是真实的。建议使用谷歌浏览器来演示&#xff0c;其他浏…
阅读更多...
Apache2.4源码安装与配置

Apache2.4源码安装与配置

环境准备 openssl-devel pcre-devel expat-devel libtool gcc libxml2-devel 这些包要提前安装&#xff0c;否则httpd编译安装时候会报错 下载源码、解压缩、软连接 1、wget下载[rootnode01 ~]# wget https://downloads.apache.org/httpd/httpd-2.4.57.tar.gz --2023-07-20 …
阅读更多...
leetcode870. 优势洗牌(java)

leetcode870. 优势洗牌(java)

优势洗牌 leetcode870. 优势洗牌题目描述双指针 排序代码 滑动窗口 leetcode870. 优势洗牌 难度 - 中等 leetcode870. 优势洗牌 题目描述 给定两个长度相等的数组 nums1 和 nums2&#xff0c;nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描…
阅读更多...
Kubernetes集群部署

Kubernetes集群部署

环境 > 192.168.50.53 k8s-master > 192.168.50.51 k8s-node1 > 192.168.50.50 k8s-node2 必须不能少于两核两G 所有主机共同操作 主机初始化配置 所有主机配置禁用防火墙和selinux [rootserver ~]# setenforce 0 [rootserver ~]# iptables -F [rootserver ~]…
阅读更多...
【MySQL】ER模型(十六)

【MySQL】ER模型(十六)

&#x1f697;MySQL学习第十六站~ &#x1f6a9;本文已收录至专栏&#xff1a;MySQL通关路 ❤️文末附全文思维导图&#xff0c;感谢各位点赞收藏支持~ ⭐学习汇总贴&#xff0c;超详细思维导图&#xff1a;【MySQL】学习汇总(完整思维导图) 一.引入 数据库设计是牵一发而动全…
阅读更多...
RocketMQ Learning(一)

RocketMQ Learning(一)

目录 一、RocketMQ 0、RocketMQ的产品发展 1、RocketMQ安装 1.1、windows下的安装 注意事项 1.2、Linux下的安装 1.3、源码的安装 1.4、控制台 2、消息发送方式 2.1、发送同步消息 2.2、发送异步消息 2.3、单向发送 3、消息消费方式 3.1、负载均衡模式&#xff0…
阅读更多...
编写第一个 React Native 程序

编写第一个 React Native 程序

React Native 目录 使用React Native CLI命令创建的目录如下图所示&#xff1a; 重要目录说明 目录说明__tests__存放测试用例的目录.bundle / config配置文件&#xff08;一般不会用到&#xff09;android 和 IOS 文件夹这两个文件夹主要是存放安卓和 ios 相关的配置文件和…
阅读更多...
XML 学习笔记 7：XSD

XML 学习笔记 7：XSD

本文章内容参考自&#xff1a; W3school XSD 教程 Extensible Markup Language (XML) 1.0 (Second Edition) XML Schema 2001 XML Schema Part 2: Datatypes Second Edition 文章目录 1、XSD 是什么2、XSD 内置数据类型 - built-in datatypes2.1、基本数据类型 19 种2.1.1、基本…
阅读更多...
【Spring Boot】构建RESTful服务 — 构建RESTful应用接口

【Spring Boot】构建RESTful服务 — 构建RESTful应用接口

构建RESTful应用接口 RESTful架构是目前最流行的互联网软件架构规范&#xff0c;是Web API&#xff08;应用编程接口&#xff09;的大趋势和主流规范&#xff0c;了解了RESTful的众多优点之后&#xff0c;接下来一步一步地学习如何使用Spring Boot构建RESTful Web API。 1.Sp…
阅读更多...
途乐证券-光伏、储能板块拉升 德业股份、固德威等大幅走高

途乐证券-光伏、储能板块拉升 德业股份、固德威等大幅走高

光伏、储能等新能源板块10日盘中震荡上扬&#xff0c;截至发稿&#xff0c;德业股份涨近8%&#xff0c;锦浪科技、固德威、阿特斯等涨逾6%&#xff0c;禾迈股份、昱能科技涨近4%。 消息面上&#xff0c;据中关村储能产业技术联盟计算&#xff0c;2021年至2023年上半年&#xff…
阅读更多...
rust关于项目结构包，Crate和mod和目录的组织

rust关于项目结构包，Crate和mod和目录的组织

rust 最近开始学习rust语言。感觉这门语言相对java确实是难上很多。开几个文章把遇到的问题记录一下 rust关于包&#xff0c;Crate 关于包&#xff0c;Crate这块先看看官方书籍怎么说的 crate 是 Rust 在编译时最小的代码单位。如果你用 rustc 而不是 cargo 来编译一个文件…
阅读更多...
最新文章

Copyright @ 2022~2023