ZOJ1586

ZOJ1586

题意:有n个人,每个人都有自己喜欢用的网络适配器,要你求连接所有人的最小费用

        构图的时候每条边的权值等于 两个人用的适配器的费用加上两个人之间网线的费用,然后求最小生成树

ZOJ1586
ZOJ1586

 1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <cstdlib>  5 #include <algorithm>  6 using namespace std;  7 #define inf 9999999  8 #define N 1005  9 int n,g[N][N],vis[N],dis[N]; 10 int cos[N]; 11 12 int prim(int st) 13 { 14 for(int i=1; i<=n; i++) 15  { 16 dis[i] = g[i][st]; 17 vis[i] = 0; 18  } 19 dis[st] = 0 ; vis[st] = 1; 20 int cost = 0; 21 for(int T=1; T<n; T++) 22  { 23 int mindis = inf , idx = -1; 24 for(int i=1; i<=n; i++) 25  { 26 if(!vis[i]&&dis[i] < mindis) 27  { 28 mindis = dis[i]; 29 idx = i; 30  } 31  } 32 cost += mindis; 33 if(idx == -1) return -1; 34 vis[idx] = 1; 35 for(int i=1; i<=n; i++) 36  { 37 if(!vis[i]&& dis[i]>g[i][idx]) 38  { 39 dis[i] = g[i][idx]; 40  } 41  } 42  } 43 return cost; 44 } 45 46 int main() 47 { 48 int T,val; 49 scanf("%d",&T); 50 while(T--) 51  { 52 for(int i=1; i<=n; i++) 53 for(int j=1; j<=n; j++) 54  { 55 if(i==j) g[i][j] =0; 56 else g[i][j]= inf; 57  } 58 59 scanf("%d",&n); 60 for(int i=1; i<=n; i++) 61 scanf("%d",&cos[i]); 62 for(int i=1; i<=n; i++) 63 for(int j=1; j<=n; j++) 64  { 65 scanf("%d",&val); 66 if(i!=j) g[i][j] = val + cos[i] + cos[j]; 67  } 68 printf("%d\n",prim(1)); 69  } 70 return 0; 71 }

View Code

 

转载于:https://www.cnblogs.com/ar940507/p/3224190.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/110063.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 云计算具有什么平台_如何搭建自己的云计算平台?「建议收藏」

    如果你的服务器很多,或者你的钱多了烧,可以考虑搭建自己的云计算平台。下面是一些开源的云计算框架和工具1.Enomalism(https://www.enomaly.com/)云计算平台。Enomalism是一个开放源代码项目,它提供了一个功能类似于EC2的云计算框架。Enomalism基于Linux,同时支持Xen和KernelVirtualMachine(KVM)。En…

  • linux MySQL启动命令

    linux MySQL启动命令linux7:1、servicemysqlstartstopstatus2、/etc/init.d/mysqlstartstop…

  • Python+PyCharm下载安装教程「建议收藏」

    Python+PyCharm下载安装教程「建议收藏」Python下载网址如下:https://www.python.org/downloads/单击Download进入下载页面,根据所用操作系统类型选择相应的Python安装文件进行下载(例如Windows7的32位操作系统选择Windowsx86executableinstaller进行下载、64位操作系统选择Windowsx86-64executableinstaller)Python安装注意勾选AddPython3.7toPATH选择,这样python的路径自动

  • Qt内存映射「建议收藏」

    Qt内存映射「建议收藏」最近在看代码的时候发现了Qt的内存映射,原来只知道MFC有内存映射机制,可以在读取大数据文件时节约读取的时间,原来Qt中也有相应的机制,其用法更简单,下面用一个小例子演示其用法#include#include#include#include#includeint

  • windows route命令[通俗易懂]

    windows route命令[通俗易懂]命令:routeprint:打印当前的路由表routedelete:删除一条路由routeadd:增加一条路由,如果最后加上–p选项,表示永久增加静态路由,重启后不会失效routechange:更改一条路由例:routeCHANGE157.0.0.0MASK255.0.0.0157.55.80.5METRIC2IF2CHANGE只用于修改网关和/或跃点数。具体场景:一台电脑通过双网卡,同时连接内网与外网.内网地址10.0.

  • Pytest(6)重复运行用例pytest-repeat[通俗易懂]

    Pytest(6)重复运行用例pytest-repeat[通俗易懂]前言平常在做功能测试的时候,经常会遇到某个模块不稳定,偶然会出现一些bug,对于这种问题我们会针对此用例反复执行多次,最终复现出问题来。自动化运行用例时候,也会出现偶然的bug,可以针对单个用例,

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号