蓝桥训练最小生成树kruscal-白红宇的个人博客

蓝桥训练最小生成树kruscal

发布日期：2021-05-14 16:48:49 浏览次数：19 分类：精选文章

本文共 1359 字，大约阅读时间需要 4 分钟。

栋栋居住在一个繁华的C市中，然而，这个城市的道路大都年久失修。市长准备重新修一些路以方便市民，于是找到了栋栋，希望栋栋能帮助他。

C市中有n个比较重要的地点，市长希望这些地点重点被考虑。现在可以修一些道路来连接其中的一些地点，每条道路可以连接其中的两个地点。另外由于C市有一条河从中穿过，也可以在其中的一些地点建设码头，所有建了码头的地点可以通过河道连接。

栋栋拿到了允许建设的道路的信息，包括每条可以建设的道路的花费，以及哪些地点可以建设码头和建设码头的花费。

市长希望栋栋给出一个方案，使得任意两个地点能只通过新修的路或者河道互达，同时花费尽量小。

样例说明

建设第2、3、4条道路，在地点4、5建设码头，总的花费为9。

数据规模和约定

对于100%的数据，1 < = n < = 10000，1 < = m < = 100000，-1000< =c< =1000，-1< =w_i< =1000，w_i≠0。

输入

输入的第一行包含两个整数n, m，分别表示C市中重要地点的个数和可以建设的道路条数。所有地点从1到n依次编号。

接下来m行，每行三个整数a, b, c，表示可以建设一条从地点a到地点b的道路，花费为c。若c为正，表示建设是花钱的，如果c为负，则表示建设了道路后还可以赚钱（比如建设收费道路）。

接下来一行，包含n个整数w_1, w_2, …, w_n。如果w_i为正数，则表示在地点i建设码头的花费，如果w_i为-1，则表示地点i无法建设码头。

输入保证至少存在一个方法使得任意两个地点能只通过新修的路或者河道互达。

输出

输出一行，包含一个整数，表示使得所有地点通过新修道路或者码头连接的最小花费。如果满足条件的情况下还能赚钱，那么你应该输出一个负数。

样例输入

5 5

1 2 4

1 3 -1

2 3 3

2 4 5

4 5 10

-1 10 10 1 1

解题报告：如果不需要通过码头，这些城市也能连通，那么加进去一个点，比较让n+1个点连通和n个点连通哪个代价小，如果城市无法联通，那么必须要用码头，输出码头的代价就行，因为道路代价可能小于0，如果两个点连通也把这条道路加进去（因为喜欢白嫖）。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            #define IL inline#define x first#define y secondtypedef long long ll;using namespace std;const int N=10010,M=210010;struct node{ int a; int b; int c; bool operator <(const node&w) const { return c
            
             >x; if(x==-1) continue; q[t++]={i,n+1,x}; } sort(q,q+m); bool flag=0; int cnt=0; ll res=0; for(int i=0;i

上一篇：蓝桥训练-拓扑排序

下一篇：问题 1445: [蓝桥杯][历届试题]最大子阵

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章