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)


相关推荐

  • Delphi源码:编辑长求字符串相似度

    Delphi源码:编辑长求字符串相似度

  • touchstart模拟点击方法[通俗易懂]

    touchstart模拟点击方法[通俗易懂]1varbtn=document.querySelectorAll(‘.所点击的类名’)[0];2varevent=document.createEvent(‘Events’);3event.initEvent(‘touchstart’,true,true);4btn.dispatchEvent(event);转载于:https…

  • Java- Set 转换成List

    Java- Set 转换成List转载:https://blog.csdn.net/fan158/article/details/28234035Set转换成List有两种方法,假设有Set集合Set<String>myset=newHashSet<String>();1.使用Arrays.asList(T…a)转换成List,此转换返回的list…

    2022年10月19日
  • HTML5管理与实际历史的分析(history物)

    HTML5管理与实际历史的分析(history物)

  • Android触摸事件_简述兴奋在突触的传递过程

    Android触摸事件_简述兴奋在突触的传递过程版本:2.0日期:2014.3.21 2014.3.29 版权:©2014kince转载注明出处  一、基本概念 在实际开发中,经常会遇到与触屏事件有关的问题,最典型的一个就是滑动冲突。比如在使用SliddingMenu菜单的时候,可能会与ViewPager或者其他的一些带有滑动事件的View相冲突,再比如ScrollView嵌套ListView相冲突等等。还有就是在自定义控件的时候,需

  • PriorityQueue(优先级队列总结)

    PriorityQueue(优先级队列总结)一,概念队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,一般出队列时,可能需要优先级高的元素先出队列 数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象。这种数据结构就是优先级队列(PriorityQueue)二,PriorityQueue的特性Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlo.

发表回复

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

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