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

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

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

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • 【WP7进阶】——分享一个可供切换状态的ListBox组件「建议收藏」

    【WP7进阶】——分享一个可供切换状态的ListBox组件

    2022年3月8日
    50
  • java拦截器放行_java拦截器放行某些请求

    java拦截器放行_java拦截器放行某些请求在java开发中,拦截器使用是很普遍的,最常用的就是登陆拦截了,然后并不是所有的请求我们都需要拦截,比如index页面的请求我们是不拦截的.通常情况下我们有两种方式:先贴出来springboot使用拦截器的case:1.自定义拦截器,实现HandlerInterceptor,也可以采用继承的方式(HandlerInterceptorAdapter),内容不重要,看过程publicclassL…

    2022年6月7日
    154
  • 理解三极管的饱和_二极管的极性判断

    理解三极管的饱和_二极管的极性判断三极管饱和(二)发表于2007-10-1723:21:36    本图片来自于<模拟集成电路的分析与设计>,用来表现三极管饱和时的carriers的分布。但此图没有按实际比例画  可以发现,在基区右侧的电子浓度高于0。而管子在放大时,电子到达该边界,立刻被反偏的电场拉到集电极了,所以,这个边缘的电子浓度在管子放大时为0。可见,管子进入饱和后,不仅这个边界的电子浓度提高,总的浓度

    2022年9月3日
    2
  • IIS 下利用UrlRewriter做图片防盗链

    IIS 下利用UrlRewriter做图片防盗链<?xmlversion=”1.0″encoding=”UTF-8″?><configuration><system.webServer><staticContent><clientCachecacheControlMode=”UseMaxAge”cacheC…

    2022年7月23日
    8
  • MFS学习总结

    MFS学习总结公司使用moosefs做图片存储,最近学习了一下,在此小小总结一下,主要分以下几部分:MFS概述、特性和新版改进MFS工作原理和设计架构MFS的安装、部署、配置MFS的高级特性MFS的性能测试MFS

    2022年8月6日
    3
  • vmware15虚拟机激活码【2021免费激活】「建议收藏」

    (vmware15虚拟机激活码)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~https://javaforall.net/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~BI7J…

    2022年3月22日
    580

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

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