链接：https://ac.nowcoder.com/acm/contest/548/C
来源：牛客网
题目描述
立华奏是一个刚刚开始学习 OI 的萌新。
最近，实力强大的 QingyuQingyu 当选了 IODS 9102 的出题人。众所周知， IODS 是一场极其毒瘤的比赛。为了在这次比赛中取得好的成绩，立华奏决定学习可能考到的每一个知识点。
在 QingyuQingyu 的博客中，立华奏得知这场比赛总共会考察选手 n 个知识点。此前，立华奏已经依靠自学学习了其中 k 个知识点。接下来，立华奏需要学习其他的知识点，每学习一个单独的知识点，需要消耗的时间为 TiTi 天。同时，某些知识点之间存在联系，可以加速学习的过程。经过计算，立华奏一共发现了其中 m 种联系，第 i 种联系可以表示为(Xi,Yi,Hi)(Xi,Yi,Hi)，其含义为“在掌握了第 XiXi 个知识点和第 YiYi 个知识点中任意一个后，学习 HiHi 天即可掌握另一个知识点”。
留给立华奏的时间所剩无几，只有 t 天，因此，她想知道自己能不能在这 t 天内学习完成所有的知识点。
最近，实力强大的 QingyuQingyu 当选了 IODS 9102 的出题人。众所周知， IODS 是一场极其毒瘤的比赛。为了在这次比赛中取得好的成绩，立华奏决定学习可能考到的每一个知识点。
在 QingyuQingyu 的博客中，立华奏得知这场比赛总共会考察选手 n 个知识点。此前，立华奏已经依靠自学学习了其中 k 个知识点。接下来，立华奏需要学习其他的知识点，每学习一个单独的知识点，需要消耗的时间为 TiTi 天。同时，某些知识点之间存在联系，可以加速学习的过程。经过计算，立华奏一共发现了其中 m 种联系，第 i 种联系可以表示为(Xi,Yi,Hi)(Xi,Yi,Hi)，其含义为“在掌握了第 XiXi 个知识点和第 YiYi 个知识点中任意一个后，学习 HiHi 天即可掌握另一个知识点”。
留给立华奏的时间所剩无几，只有 t 天，因此，她想知道自己能不能在这 t 天内学习完成所有的知识点。
输入描述:
本题输入量较大，请注意使用效率较高的读入方式
输入的第一行包含四个整数 n, m, k, t，含义见上所述。
接下来一行，包含 n 个整数，依次表示 T1,T2,⋯,TnT1,T2,⋯,Tn
接下来一行，包含 k 个整数，表示立华奏已经学习过的知识点。如果 k=0，则此处为一空行。
接下来 m 行，每行 3 个整数 Xi,Yi,HiXi,Yi,Hi，描述一种联系。
输出描述:
如果立华奏能够学习完所有的知识点，输出一行 Yes。否则输出 No
示例1
输入
4 3 2 5
4 5 6 7
2 3
1 2 3
1 3 2
3 4 2
输出
Yes
思路:创建一个虚拟节点(我是用0) 然后对于已学的点和没学 以及有关联的点进行建边 最后Kruska跑一边
但是这题卡常 所以写法上要尽量优化
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define ll long long int
using namespace std;
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int moth[]={,,,,,,,,,,,,};
int dir[][]={, ,, ,-, ,,-};
int dirs[][]={, ,, ,-, ,,-, -,- ,-, ,,- ,,};
const int inf=0x3f3f3f3f;
const ll mod=1e9+;
const int maxn=7e6 + ;
inline int read(){
char ch = getchar(); ll x = , f = ;
while(ch < '' || ch > '') {if(ch == '-') f = -; ch = getchar();}
while('' <= ch && ch <= '') {x = x * + ch - ''; ch = getchar();}
return x * f;
}
struct node{
int to;
int from;
int v;
friend bool operator < (node a,node b){
return a.v<b.v;
}
};
node edge[];
int f[maxn];
int cnt=;
int n,m,k;
ll t;
void add(int from,int to,int va){ //加边
edge[++cnt].to=to;
edge[cnt].v=va;
edge[cnt].from=from;
}
int find(int x){
if(x!=f[x])
f[x]=find(f[x]);
return f[x];
}
int main(){
//ios::sync_with_stdio(false);
n=read(); m=read(); k=read();
t=read();
int time;
int learn;
int x,y,h;
for(int i=;i<=n;i++){ //给虚拟节点加上初始边
time=read();
add(,i,time);
f[i]=i;
}
for(int i=;i<=k;i++){
learn=read(); //已经学习的点就和0关联起来就行
f[find(learn)]=;
}
for(int i=;i<=m;i++){ //关联点加边
x=read(); y=read(); h=read();
add(x,y,h);
}
sort(edge+,edge++cnt);
ll ans=;
int num=k;
for(int i=;i<=cnt;i++){
if(find(edge[i].from)!=find(edge[i].to)){
// cout<<edge[i].from<<" "<<edge[i].to<<endl;
f[find(edge[i].from)]=find(edge[i].to);
++num;
ans+=edge[i].v;
}
if(num==n||ans>t){
break;
}
}
if(ans>t)
puts("No");
else
puts("Yes");
}