链接：https://ac.nowcoder.com/acm/contest/330/G
来源：牛客网
Applese 的毒气炸弹
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
众所周知，Applese 是个很强的选手，它的化学一定很好。
今天他又AK了一套题觉得很无聊，于是想做个毒气炸弹玩。
毒气炸弹需要 k 种不同类型元素构成，Applese一共有 n 瓶含有这些元素的试剂。
已知元素混合遵循 m 条规律，每一条规律都可以用 "x y c" 描述。
表示将第 x 瓶试剂混入第 y 瓶试剂或者把第 y 瓶试剂混入第 x 瓶试剂，需要消耗 c 的脑力。
特别地，除了这 m 条规律外，Applese 可以将任意两瓶相同元素的试剂混合，且不需要消耗脑力。
输入描述:
第一行为三个整数 n, m, k 表示 Applese 拥有的试剂的数量，混合规律的数量和所需的元素种类数。
第二行为 n 个整数 a1,a2,…,ana1,a2,…,an，分别表示每一瓶试剂的元素类型。
接下来m行，每行三个整数 x, y, c，含义如题目描述中所述。不保证 x, y的试剂种类不同。
输出描述:
输出一个正整数表示最小的耗费脑力。特别地，如果无法合成出毒气炸弹，输出 "-1"。
备注:
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 <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #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<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #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<<"== [ "<<x<<" ] =="<<endl; using namespace std; typedef long long ll; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;} inline void getInt(int* p); const int maxn=1000010; const int inf=0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ struct Edge { int f,t,w; Edge(){} Edge(int ff,int tt,int ww) { f=ff; t=tt; w=ww; } }; std::vector<Edge> edge; bool cmp(Edge a,Edge b) { return a.w<b.w; } // 并查集部分 int fa[maxn]; int findpar(int x) { if(fa[x]==x) return x; else return fa[x]=findpar(fa[x]); } void initufs(int n) { repd(i,1,n) { fa[i]=i; } } int n,m,k; // int a[maxn]; ll Kruskal() { ll res=0ll; initufs(n); int cnt=0;// 记录了MST加入了几个节点 for(int i=0;i<edge.size();i++) { int u=findpar(edge[i].f); int v=findpar(edge[i].t); if(u==v) continue; fa[u]=v; // merge res+=edge[i].w; cnt++; if(cnt==k-1) // 已经加满了树 break; } if(cnt!=k-1) return -1; else return res; } int main() { scanf("%d %d %d",&n,&m,&k); repd(i,1,n) { scanf("%d",&a[i]); } int u,v,w; repd(i,1,m) { scanf("%d %d %d",&u,&v,&w); u=a[u];v=a[v]; if(u==v) continue; if(u>=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‘; } } }