Applese 的毒气炸弹 G 牛客寒假算法基础集训营4（图论+最小生成树）-白红宇

Applese 的毒气炸弹 G 牛客寒假算法基础集训营4（图论+最小生成树）

阅读量：5131 次

发布时间：2019-06-13

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

链接：

来源：牛客网

Applese 的毒气炸弹

时间限制：C/C++ 2秒，其他语言4秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

众所周知，Applese 是个很强的选手，它的化学一定很好。

今天他又AK了一套题觉得很无聊，于是想做个毒气炸弹玩。

毒气炸弹需要 k 种不同类型元素构成，Applese一共有 n 瓶含有这些元素的试剂。

已知元素混合遵循 m 条规律，每一条规律都可以用 "x y c" 描述。

表示将第 x 瓶试剂混入第 y 瓶试剂或者把第 y 瓶试剂混入第 x 瓶试剂，需要消耗 c 的脑力。

特别地，除了这 m 条规律外，Applese 可以将任意两瓶相同元素的试剂混合，且

不需要消耗脑力。

Applese 想要配出毒气炸弹，就需要使 S 中含有

输入描述:

第一行为三个整数 n, m, k 表示 Applese 拥有的试剂的数量，混合规律的数量和所需的元素种类数。 第二行为 n 个整数 a1,a2,…,ana1,a2,…,an，分别表示每一瓶试剂的元素类型。 接下来m行，每行三个整数 x, y, c，含义如题目描述中所述。不保证 x, y的试剂种类不同。

输出描述:

输出一个正整数表示最小的耗费脑力。特别地，如果无法合成出毒气炸弹，输出 "-1"。

示例1

输入

6 8 21 1 1 2 2 21 2 12 3 21 3 33 4 64 5 14 6 35 6 21 6 2

输出

备注:

1≤n,k,m≤1051≤n,k,m≤105 1≤x,y≤n,x≠y1≤x,y≤n,x≠y 1≤c≤109 思路： 看成一张图，就是把同类元素的试剂当作一个点之后，求这个图的最小生成树。 然后用你最喜欢的求MST的算法求解就好。注意判不连通的情况。 细节见代码

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 #define rt return#define sz(a) int(a.size())#define all(a) a.begin(), a.end()#define rep(i,x,n) for(int i=x;i
                 
                  #define pll pair
                  
                   #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define MS0(X) memset((X), 0, sizeof((X)))#define MSC0(X) memset((X), '\0', sizeof((X)))#define pb push_back#define mp make_pair#define fi first#define se second#define eps 1e-6#define gg(x) getInt(&x)#define db(x) cout<<"== [ "<
                   
                    <<" ] =="<
                    
                      edge;bool cmp(Edge a,Edge b){ return a.w
                     
                      =1&&u<=k&&v>=1&&v<=k) { edge.push_back(Edge(u,v,w)); } } sort(edge.begin(),edge.end(),cmp); ll res=Kruskal(); printf("%lld\n",res ); return 0;}inline void getInt(int* p) { char ch; do { ch = getchar(); } while (ch == ' ' || ch == '\n'); if (ch == '-') { *p = -(getchar() - '0'); while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 - ch + '0'; } } else { *p = ch - '0'; while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 + ch - '0'; } }}