Tachibana Kanade Loves Review

题目链接：Tachibana Kanade Loves Review

一道最小生成树好题。

考虑建图：
建立一个虚拟节点，对于已经完成的k个知识点，我们直接让虚拟节点与其相连。

然后对于m个关系，我们让其相连，最后求最下生成树即可。（可自己证明正确性）。

不过这道题卡常很恶心，我们可以玄学并查集的merge，因为数据很有可能卡我们并查集，卡成一条链，然后我们就随机合并，既可以保证近似的log的高度，然后加上路径压缩就可以跑得很快。

不过还有一种，因为数据很小，所以我们可以基数排序，消去一个log。

听说大神能贪心过！！！TQL！！！

注意：不要全开long long，会TLE。跑得不如int快，个别long long即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,k,s,cnt,f[N],tot; 
long long res,T;
struct node{
	int u,v,w;
}t[N*6];
int cmp(node a,node b){
	return a.w<b.w;
}
inline int read()
{
    int s = 0; char ch = getchar();
    while(!(ch >= '0' && ch <= '9' )) ch = getchar();
    while(ch >= '0' && ch <= '9'){s = s*10+ch-'0'; ch = getchar();}
    return s;
}
int find(int x){
	return x==f[x]?x:f[x]=find(f[x]);
}
signed main(){
	n=read(); m=read(); k=read(); scanf("%lld",&T); s=n+1;	f[s]=s;
	for(int i=1;i<=n;i++){
		f[i]=i;	int x;	x=read();	t[++tot]={s,i,x};
	}
	while(k--){
		int x;	x=read();	f[x]=s;
	}
	while(m--){
		int a,b,c;	a=read(); b=read(); c=read(); t[++tot]={a,b,c};
	}
	sort(t+1,t+1+tot,cmp);
	for(int i=1;i<=tot;i++){
		int fa=find(t[i].u); int fb=find(t[i].v);
		if(fa!=fb){
			res+=t[i].w;
			if(i&1)	f[fa]=fb;	else	f[fb]=fa;
			if(res>T)	break;
		}
	}
	puts(res>T?"No":"Yes");
	return 0;
}