NYOJ38-布线问题

简介: NYOJ38-布线问题


布线问题

时间限制:1000 ms  |  内存限制:65535 KB

难度:4

描述

南阳理工学院要进行用电线路改造,现在校长要求设计师设计出一种布线方式,该布线方式需要满足以下条件:

1、把所有的楼都供上电。

2、所用电线花费最少

输入

第一行是一个整数n表示有n组测试数据。(n<5)

每组测试数据的第一行是两个整数v,e.

v表示学校里楼的总个数(v<=500)

随后的e行里,每行有三个整数a,b,c表示a与b之间如果建铺设线路花费为c(c<=100)。(哪两栋楼间如果没有指明花费,则表示这两栋楼直接连通需要费用太大或者不可能连通)

随后的1行里,有v个整数,其中第i个数表示从第i号楼接线到外界供电设施所需要的费用。( 0<e<v*(v-1)/2 )

(楼的编号从1开始),由于安全问题,只能选择一个楼连接到外界供电设备。

数据保证至少存在一种方案满足要求。

输出

每组测试数据输出一个正整数,表示铺设满足校长要求的线路的最小花费。

样例输入

1
4 6
1 2 10
2 3 10
3 1 10
1 4 1
2 4 1
3 4 1
1 3 5 6

样例输出

4

来源

[张云聪]原创

 

 

 

 

题目分析:

典型的最小生成数问题

第一种kruskal算法

其实kruskal算法就是并查集联通路问题只不过现在每个边有了价值权值

 

克鲁斯卡尔(Kruskal)算法(只与边相关)

 

算法描述:克鲁斯卡尔算法需要对图的边进行访问,所以克鲁斯卡尔算法的时间复杂度只和边又关系,可以证明其时间复杂度为O(eloge)。

算法过程:

1.将图各边按照权值进行排序

2.将图遍历一次,找出权值最小的边,(条件:此次找出的边不能和已加入最小生成树集合的边构成环),若符合条件,则加入最小生成树的集合中。不符合条件则继续遍历图,寻找下一个最小权值的边。

3.递归重复步骤1,直到找出n-1条边为止(设图有n个结点,则最小生成树的边数应为n-1条),算法结束。得到的就是此图的最小生成树。

 

克鲁斯卡尔(Kruskal)算法因为只与边相关,则适合求稀疏图的最小生成树。而prime算法因为只与顶点有关,所以适合求稠密图的最小生成树。

 

 

 

 

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<climits>
using namespace std;
typedef struct node{
  int s;
  int e;
  int w;
}Edge;
 Edge edge[260000];
 int f[550];
 int find(int x){
  if(x==f[x])
    return x;
  f[x]=find(f[x]);
    return f[x];
 }
 int m,minn=INT_MAX;
 int num,road,sum;
 void kruskal(){
    int ans=0;
    sum=minn;
    for(int i=0;i<road;i++){
      int x1=find(edge[i].s);
      int y1=find(edge[i].e);
      if(x1!=y1){
        f[x1]=y1;
        sum+=edge[i].w;
        ans++;
        if(ans==num-1) break;
      }
    }
 }
 bool cmp(node a,node b)
 {
  return a.w<b.w;
 }
int main()
{
  int n;
  cin>>n;
  while(n--)
  {
//    int num,road;
    cin>>num>>road;
    for(int i=0;i<road;i++)
      cin>>edge[i].s>>edge[i].e>>edge[i].w;
    
    for(int i=0;i<num;i++){
      cin>>m;
      minn=min(minn,m);
    }
    sort(edge,edge+road,cmp);
    for(int i=0;i<=num;i++)
      f[i]=i;
    kruskal();
    printf("%d\n",sum);
  }
  return 0;
 } 

 

 

 

 

 

 

limits.h  头文件里包含了数据最值数据

标准库

第二种 prime算法

 

最小生成树prime算法详解

 

 

 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <iostream>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=500+20;
int map[maxn][maxn],mark[maxn],dist[maxn];
int v,e;
int prime()
{
  int pos,ans,sum=0;
  memset(mark,0,sizeof(mark));
    memset(dist,INF,sizeof(dist));
  for(int i=1;i<=v;i++)
    dist[i]=map[1][i];
  dist[1]=0;
  mark[1]=1;
  pos=-1;
  for(int i=2;i<=v;i++){
    ans=INF;
    for(int j=1;j<=v;j++){
      if(!mark[j]&&dist[j]<ans){
        ans=dist[j];
        pos=j;
      }
    }
    sum+=ans;
    mark[pos]=1;
    for(int j=1;j<=v;j++){
      if(!mark[j]&&map[pos][j]<dist[j])
        dist[j]=map[pos][j];
    }
  }
  return sum;
}
int main()
{
  int n;
  int a,b,c;
    scanf("%d",&n);
    while(n--)
    {
        cin>>v>>e;
        for(int i=1;i<=v;i++)
           for(int j=1;j<=v;j++)
           {
              map[i][j]=map[j][i]=INF;
              if(i==j) map[i][j]=map[j][j]=0;
       }
              
    
        for(int i=1;i<=e;i++){
            scanf("%d%d%d",&a,&b,&c);
            map[a][b]=map[b][a]=c;
        }
        int m,minn=INT_MAX;
        for(int j=1;j<=v;j++){
          cin>>m;
      minn=min(minn,m); 
    }
        printf("%d\n",prime()+minn);
    }
    return 0;
}

 

 


目录
相关文章
pip镜像源大全及配置
在中国使用pip时,可以配置国内镜像源来提高安装速度和稳定性。以下是一些常见的国内镜像源:
17106 0
|
开发工具
完全解决zsh compinit: insecure directories, run compaudit for list. Ignore insecure directories
完全解决zsh compinit: insecure directories, run compaudit for list. Ignore insecure directories
2028 0
完全解决zsh compinit: insecure directories, run compaudit for list. Ignore insecure directories
|
机器学习/深度学习 供应链 算法
Python配对交易策略统计套利量化交易分析股票市场
Python配对交易策略统计套利量化交易分析股票市场
|
3天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
14天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1305 5
|
13天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1332 87
|
2天前
|
弹性计算 安全 数据安全/隐私保护
2025年阿里云域名备案流程(新手图文详细流程)
本文图文详解阿里云账号注册、服务器租赁、域名购买及备案全流程,涵盖企业实名认证、信息模板创建、域名备案提交与管局审核等关键步骤,助您快速完成网站上线前的准备工作。
184 82
2025年阿里云域名备案流程(新手图文详细流程)