最小生成树拓展应用

文章目录

  • 最小生成树拓展应用
      • 理论基础
    • 题单
        • 1. [新的开始](https://www.acwing.com/problem/content/1148/)
        • 2. [北极通讯网络](https://www.acwing.com/problem/content/1147/)
        • 3. [走廊泼水节](https://www.acwing.com/problem/content/348/)
        • 4. [秘密的牛奶运输](https://www.acwing.com/problem/content/1150/)

最小生成树拓展应用

  • 虚拟源点
  • kruskal拓展
  • 次小生成树

理论基础

  1. 任意一棵最小生成树一定可以包含无向图中权值最小的边
  2. 给定一张无向图 G = ( V , E ) , n = ∣ V ∣ , m = ∣ E ∣ G=(V,E),n=|V|,m=|E| G=(V,E),n=∣V∣,m=∣E∣，从E中选出k<n-1条边构成G的加一个生成森林。若再从剩余的m-k条边中选n-1-k条边添加到生成森林中，使其成为G的生成树，并且选出的边的权值之和最小。则该生成树一定可以包含m-k条边中连接生成森林的两个不连通接节点的权值最小的边

题单

1. 新的开始

第一眼：

  • 要么和其他矿井建立电网共用一个发电站，要么自建发电站
  • 只有当自建站比建电网费用要小时，才自建站
  • 把自环也当成一条边放进去sort，当用不到点时就结束？
  • 已经有电力供应的也可以给其他供应，意思就是进入了生成树就具有供电能力，因此不用担心加进来的边是那个点拉进来的

思考：

感觉是可以prim算法的

  • 为什么prim要过还得有 g [ j ] [ i ] = m i n ( g [ j ] [ i ] , v ) g[j][i]=min(g[j][i],v) g[j][i]=min(g[j][i],v),一篇ac题解

小试牛刀，没过

听y话：

建立一个超级源点，可以解决从哪个点开始的问题，如果只选最小点开始，会把其他自环(也应当看成一条边)忽略而没考虑到

#include<bits/stdc++.h>

using namespace std;
const int N=310,INF=0x3f3f3f3f;
int g[N][N],v[N],d[N],st[N];
int res,n;

void prim(int s){
  memset(d,0x3f,sizeof d);
  d[s]=g[s][s];

  for(int i=1;i<=n;i++){
    int t=-1;
    for(int j=1;j<=n;j++){
      if(!st[j]&&(t==-1||d[t]>d[j])){
        t=j;
      }
    }
    st[t]=1;
    //cout<<t<<","<<d[t]<<' ';
    res+=d[t];
    for(int j=1;j<=n;j++) d[j]=min(d[j],g[t][j]);
  }
}

signed main(){
  cin>>n;
  //memset(g,0x3f,sizeof g);
  int minx=INF,mindex=0;
  for(int i=1;i<=n;i++){
    cin>>g[i][i];
    for(int j=1;j<=n;j++){
      g[j][i]=min(g[j][i],g[i][i]);
    }
    if(minx>g[i][i]){
      mindex=i;
      minx=g[i][i];
    }
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      int x;
      cin>>x;
      if(i!=j) g[i][j]=x;
    }
  }
  prim(mindex);
  //cout<<endl;
  cout<<res<<endl;
  return 0;
}

手搓建立一个超级源点，ac了，prim算法

#include<bits/stdc++.h>

using namespace std;
int n;
const int N=310;
int g[N][N],st[N],d[N];
int res;

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


signed main(){
  cin>>n;
  for(int i=1;i<=n;i++){
    int x;
    cin>>x;
    g[0][i]=g[i][0]=x;
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      cin>>g[i][j];
    }
  }
  prim();
  cout<<res<<endl;
  return 0;
}
2. 北极通讯网络

第一眼：

  • 加了k限制的最小生成树，能不能用一个变量去计数呢？
  • 挺复杂的一道题，看的第一遍没懂

听y讲：

  • 涉及到通信问题——”中转“，卫星通信(有限)，无线收发器(无限)
  • 用并查集就不需要二分了

思考：

  • 要找到最小的d，那一定是先让小边进入kruskal
  • 关于连通块的问题
    • 并查集
    • bfs和dfs有联想到
  • 有点明白，因为这道题一开始并没有直接相连的点，所有点都是独立的，我们要去找最小生成树的话，在本题用kruskal的时候，枚举一次，连通块的个数就会减一
  • 找到第一个能让剩余连通块个数小于等于k的边就行了

版本一过啦，烙铁～

#include<bits/stdc++.h>

using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N=510,M=N*N;
PII dian[N];
int fa[N];
int n,k;

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

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

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

signed main(){
  cin>>n>>k;
  for(int i=1;i<=n;i++) fa[i]=i;
  for(int i=1;i<=n;i++){
    int x,y;
    cin>>x>>y;
    dian[i]={x,y};
  }
  int cnt=0;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      double dist=get_dis(dian[i],dian[j]);
      e[cnt++]={i,j,dist};
    }
  }
  
  sort(e,e+cnt);
  int count=n;
  double res=0;
  for(int i=0;i<cnt;i++){
    int a=e[i].x,b=e[i].y;
    double c=e[i].z;
    a=find(a),b=find(b);
    if(a!=b){
      fa[a]=b;
      res=c;
      count--;
    }
    if(count<=k){
      break;
    }
  }
  printf("%.2f\n",res);
  return 0;
}
3. 走廊泼水节

第一眼：

  • 何为完全图（俩俩之间有边就是完全图）image-20240627183647506
  • 求的是增加的，而不总的，好像可以kruskal解决，但是得知道完全图是什么意思

听y说：

  • 按照什么样的顺序连接能够得到最小值
  • 新边 < w i w_i wi​ ❌——》不满足生成树定义
  • 新边 = w i w_i wi​ ❌——》要求生成树唯一

思考：

  • 关于 新边 〉= w i + 1 w_i+1 wi​+1 为什么构造的生成树一定是唯一的
    • 因为你要求最小生成树，如果 w i + 1 w_i+1 wi​+1 不唯一，那就意味着有 w i w_i wi​可以被添加到里面去，那求的原来的生成树就不是最小生成树了，和原树是一个最小生成树矛盾。
  • 怎么把两个集合的所有点连起来
    • 用并查集维护各连通块点的个数
  • 优质题解image-20240628004028620
#include<bits/stdc++.h>

using namespace std;
int n;
const int N=6e3+10,M=N*N;
int fa[N],psize[N];

struct edge{
  int x,y,z;
  bool operator<(const edge& M)const{
    return z<M.z;
  }
}edges[M];

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

signed main(){
  int t;
  cin>>t;
  while(t--){
    cin>>n;
    for(int i=1;i<=n;i++) fa[i]=i,psize[i]=1;
    for(int i=0;i<n-1;i++){
      int a,b,c;
      cin>>a>>b>>c;
      edges[i]={a,b,c};
    }
		sort(edges,edges+n-1);
    int res=0;
    for(int i=0;i<n-1;i++){
      int a=find(edges[i].x),b=find(edges[i].y),c=edges[i].z;
      if(a!=b){
        res+=((psize[a]*psize[b]-1)*(c+1));
        //因为是还需要多少边，所以原本存在的c不用加
        psize[b]+=psize[a];
        fa[a]=b;
      }
    }
    cout<<res<<endl;
  }
  return 0;
}
4. 秘密的牛奶运输

第一眼：

  • 又是奶牛，又是usaco
  • 费用第二小怎么搞次最小生成树
  • 费用第二严格大于费用最小，距离z代表着成本

思考：

  • 可不可以找到最小生成树的后一条边（这个边需要满足能生成树）当作答案？

  • 啥玩意image-20240628005813618

听y说：

  • image-20240628012126169
  • 注意总长度会爆int，要开long long
#include<bits/stdc++.h>

#define int long long 
using namespace std;
int n,m;
const int N=510, M=1e4+10;
int fa[N],d1[N][N],d2[N][N];
//d1存储的是两点之间路径的最长的边
//d2存储的是两点之间路径的次长的边
int h[N],e[2*N],ne[2*N],w[2*N],idx;
//因为是树的结构，可以看成每个点最多有两个子节点

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

struct edge{
  int x,y,z;
  bool f;
  bool operator<(const edge& M)const{
    return z<M.z;
  }
}es[M];

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

//d1,d2形式参数的类型是一维数组，而实参穿的也是一维数组的地址
void dfs(int u,int father,int dmax1,int dmax2,int d1[],int d2[]){
  d1[u]=dmax1,d2[u]=dmax2;
  for(int i=h[u];~i;i=ne[i]){
    int j=e[i];
    if(j!=father){
      int td1=dmax1,td2=dmax2;
      if(w[i]>td1) td2=td1,td1=w[i];
      else if(w[i]<td1&&w[i]>td2) td2=w[i];
      dfs(j,u,td1,td2,d1,d2);
    }
  }
}

signed main(){
  cin>>n>>m;
  memset(h,-1,sizeof h);
  //memset(d1,0x3f,sizeof d1);
  //memset(d2,0x3f,sizeof d2);
  for(int i=1;i<=n;i++) fa[i]=i;
  for(int i=0;i<m;i++){
    int x,y,z;
    cin>>x>>y>>z;
    es[i]={x,y,z};
  }
  sort(es,es+m);
  //求最小生成树
  int sum=0;
  for(int i=0;i<m;i++){
    int a=es[i].x,b=es[i].y,c=es[i].z;
    int pa=find(a),pb=find(b);
    if(pa!=pb){
      fa[pa]=pb; //这里需要找到各自的父节点然后再创建连接
      sum+=c;
      add(a,b,c),add(b,a,c);
      es[i].f=true;
    }
  }
  //以每个点为根找到其与其他点之间的最远距离？
  for(int i=1;i<=n;i++) dfs(i,-1,-1e9,-1e9,d1[i],d2[i]);
  
  //debug dfs找任意两点之间路径最长边和次长边
  //for(int i=1;i<=n;i++){
  //    cout<<i<<":"<<endl;
  //    int k=h[i];
  //    for(int j=k;~j;j=ne[j]){
  //        cout<<e[j]<<","<<d1[i][e[j]]<<","<<d1[i][e[j]]<<" ";
  //    }
  //    cout<<endl;
  //}
  //为什么debug代码打完就过了？
  
	int res=1e18;
  for(int i=0;i<m;i++){
    bool f=es[i].f;
    int a=es[i].x,b=es[i].y,c=es[i].z;
    if(!f){
      if(c>d1[a][b])
				res=min(res,sum+c-d1[a][b]);
      else if(c>d2[a][b]){
        res=min(res,sum+c-d2[a][b]);
      }
    }
  }
  cout<<res<<endl;
  return 0;
}

后台测试样例

4 4
1 2 1
2 3 2
3 4 1
2 4 2

5

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

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

相关文章

Verystar费芮荣获腾讯游戏人生平台2023年度“最佳营销服务商”奖项

Verystar费芮荣获腾讯游戏人生平台2023年度“最佳营销服务商”奖项

先导&#xff1a;Verystar费芮是电通旗下拥有领先的技术支持、数据驱动的客户体验管理 (CXM) 公司&#xff0c; 6月27日腾讯游戏人生合作伙伴大会&#xff0c;宣布 Verystar费芮连续四年荣获“最佳营销服务商”奖项。 6月27日&#xff0c;2024年腾讯游戏人生合作伙伴大会在深圳…
阅读更多...
【知识图谱系列】Neo4j使用Py2neo与python进行链接

【知识图谱系列】Neo4j使用Py2neo与python进行链接

目录 一、安装py2neo 二、打开Neo4j 三、使用Python操作Neo4j 一、安装py2neo pip install --upgrade py2neo -i https://pypi.tuna.tsinghua.edu.cn/simple 可以先阅读下文档&#xff1a;https://py2neo.org/v4/index.html 这个文档里有好多关于这个工具包的API介绍&#x…
阅读更多...
从赛题切入谈如何学习数学建模

从赛题切入谈如何学习数学建模

1.引言 &#xff08;1&#xff09;今天学习了这个汪教授的这个视频&#xff0c;主要是对于一个赛题的介绍讲解&#xff0c;带领我们通过这个赛题知道数学建模应该学习哪些技能&#xff0c;以及这个相关的经验&#xff0c;我感觉这个还是让我自己受益匪浅的 &#xff08;2&…
阅读更多...
Openldap安装部署及Gitea简单配置使用

Openldap安装部署及Gitea简单配置使用

Openldap安装部署及Gitea简单配置使用 一.安装Openldap #拉取镜像 docker pull osixia/openldap:latestdocker run \ -d \ -p 389:389 \ -p 636:636 \ -v /home/data/openldap/local:/usr/local/ldap \ -v /home/data/openldap/lib:/var/lib/ldap \ -v /home/data/openldap/s…
阅读更多...
数据分析报告制作的结构和思路整理

数据分析报告制作的结构和思路整理

先画重点&#xff1a;一份分析报告的制作&#xff0c;目前的市场的分析步骤是优先找一些别人的研究报告&#xff0c;现成的东西&#xff0c;重点是要好好总结业务逻辑和潜在运营可能&#xff0c;这也是一位优秀数据分析师的价值体现。 举个例子&#xff0c;以目前小说短剧赛道的…
阅读更多...
C语言指针速成下篇

C语言指针速成下篇

c语言的指针下篇终于迎来了收尾&#xff0c;那么废话不多说&#xff0c;我们直接进入正题 指针访问数组 # include <stdio.h> int main () { int arr[ 10 ] { 0 }; // 输⼊ int i 0 ; int sz sizeof (arr)/ sizeof (arr[ 0 ]); // 输⼊ int * p arr //这…
阅读更多...
Ubuntu+Apache2 搭建Gerrit 环境

Ubuntu+Apache2 搭建Gerrit 环境

一、前言 时隔多年&#xff0c;好久没有更新CSDN 博客了&#xff0c;主要原因有如下两点&#xff1a; 1、平时工作繁忙&#xff0c;无暇更新。 2、工作内容涉及信息安全&#xff0c;一些工作经验积累不便更新到互联网上。 最近一直在折腾搭建Gerrit 环境&#xff0c;最开始是…
阅读更多...
PHP 超级全局变量详解

PHP 超级全局变量详解

在PHP编程中&#xff0c;超级全局变量&#xff08;Super Global Variables&#xff09;是一种特殊的变量&#xff0c;可以在脚本的任何地方访问&#xff0c;而不受作用域限制。它们被设计用于在不同的脚本文件、函数和类之间共享数据&#xff0c;是PHP语言中非常重要和实用的特…
阅读更多...
GPU设置

GPU设置

GPU降温测试 前提 同一个训练程序&#xff0c;使用8块GPU&#xff0c;GPU使用率基本全程>90%&#xff0c;GPU为1080 Ti 限制最高功率效果 不限制最高功率(默认最高功率250W)&#xff1a;最高温度85&#xff0c;大多时间在75-85之间 将最高功率限制为150W&#xff1a;最高…
阅读更多...
【ACM_2023】3D Gaussian Splatting for Real-Time Radiance Field Rendering

【ACM_2023】3D Gaussian Splatting for Real-Time Radiance Field Rendering

【ACM_2023】3D Gaussian Splatting for Real-Time Radiance Field Rendering 一、前言Abstract1 INTRODUCTION2 RELATED WORK2.1 Traditional Scene Reconstruction and Rendering2.2 Neural Rendering and Radiance Fields2.3 Point-Based Rendering and Radiance Fields 3 O…
阅读更多...
新手向导：掌握Axure RP的第一步

新手向导：掌握Axure RP的第一步

其实很多时候&#xff0c;我们很容易把教程做得太复杂&#xff0c;让学生失去重点被复杂的理论吓到。入门基础的时候只需要先弄清楚两个核心内容&#xff0c;学起来就容易多了:一是简单了解这个软件&#xff0c;二是学习这个软件的基本操作。所以如果你问我什么是好的 Axure RP…
阅读更多...
python中pip换源

python中pip换源

目录 1. 背景2. Python 的 pip 换源2.1 临时换源&#xff08;命令行中使用参数&#xff09;2.2 永久换源&#xff08;修改配置文件&#xff09;2.2.1 Windows系统2.2.2 Linux/macOS系统 2.3 使用 pip-config 命令换源&#xff08;Linux/macOS 特定&#xff09; 3. 常用的 PyPI …
阅读更多...
U盘数据被删，四个补救措施要收藏好！

U盘数据被删，四个补救措施要收藏好！

在日常工作及学习过程中&#xff0c;大家都会频繁使用U盘进行数据储存与转移。然而因操作失误&#xff0c;如&#xff1a;手动误删、直接清空或格式化等&#xff0c;将会造成一些重要的数据遗失&#xff0c;并且在面临此状况时&#xff0c;就需要找到一个有效的方法去恢复了。那…
阅读更多...
C语言分支和循环（上）

C语言分支和循环（上）

C语言分支和循环&#xff08;上&#xff09; 1. if语句1.1 if1.2 else1.3 分支中包含多条语句1.4 嵌套if1.5 悬空else问题 2. 关系操作符3. 条件操作符4. 逻辑操作符&#xff1a;&&,||,&#xff01;4.1 逻辑取反运算符4.2 与运算符4.3 或运算符4.4 练习&#xff1a;闰年…
阅读更多...
GRS认证流程是什么？

GRS认证流程是什么？

GRS认证的认证流程主要包括以下几个步骤&#xff1a; 1. 提交申请 首先&#xff0c;企业需要向GRS认证机构提交认证申请&#xff0c;并提供相关的企业信息和产品信息。这通常包括企业的基本信息、生产工厂信息、产品范围、生产流程等。 2. 合同评审 认证机构会对企业提交的…
阅读更多...
【php】【mysql】【layui】 原生初级简易留言簿系统成品代码动态网站开发网页WEB浏览器端B/S结构

【php】【mysql】【layui】 原生初级简易留言簿系统成品代码动态网站开发网页WEB浏览器端B/S结构

更多项目点击&#x1f446;&#x1f446;&#x1f446;完整项目成品专栏 【php】【mysql】【layui】 原生初级简易留言簿系统成品代码动态网站开发网页WEB浏览器端B/S结构 获取源码方式项目说明&#xff1a;文件包含&#xff1a;项目运行环境项目运行截图 获取源码方式 加Q群…
阅读更多...
如何快捷批量处理图片？图片批量改大小、格式、尺寸的方法

如何快捷批量处理图片？图片批量改大小、格式、尺寸的方法

怎么把图片批量修改成同一尺寸呢&#xff1f;图片在日常工作和生活中有很多的用途&#xff0c;每天都会需要使用不同类型的图片来获取我们需要的内容。在使用图片的时候&#xff0c;经常会遇到比较常见的几个限制问题&#xff0c;比如图片大小、图片尺寸、图片格式等&#xff0…
阅读更多...
Google发布Gemma 2轻量级开放模型 以极小的成本提供强大的性能

Google发布Gemma 2轻量级开放模型 以极小的成本提供强大的性能

除了 Gemini 系列人工智能模型外&#xff0c;Google还提供 Gemma 系列轻量级开放模型。今天&#xff0c;他们发布了 Gemma 2&#xff0c;这是基于全新架构设计的下一代产品&#xff0c;具有突破性的性能和效率。 Gemma 2 有两种规格&#xff1a;90 亿 (9B) 和 270 亿 (27B) 个参…
阅读更多...
ElasticSearch中的BM25算法实现原理及应用分析

ElasticSearch中的BM25算法实现原理及应用分析

文章目录 一、引言二、BM25算法实现原理BM25算法的实现原理1. 词频&#xff08;TF&#xff09;&#xff1a;2. 逆文档频率&#xff08;IDF&#xff09;&#xff1a;3. 长度归一化&#xff1a;4. BM25评分公式&#xff1a; BM25算法示例 三、BM25算法在ElasticSearch中的应用分析…
阅读更多...
MTK8786/MT8786芯片性能参数_规格书_datasheet

MTK8786/MT8786芯片性能参数_规格书_datasheet

联发科MT8786(MTK8786)处理器采用了台积电12纳米FinFET技术&#xff0c;由2个Cortex A75核心和6个Cortex A55核心组成&#xff0c;其中大核A75主频为2.0GHz&#xff0c;GPU采用了ARM Mali-G52。MTK8786芯片设计极大地提升了智能设备的性能和安全等级。 MT8786采用了安全的ISP设…
阅读更多...
最新文章

Copyright @ 2022~2023