题目地址
题解
虚点这种东西还是没有掌握好啊。
考虑建一个虚点，向已经学会的东西连一条边权为0的边，关系正常连边，单独学的从虚点连一条边过去。
然后做一遍最小生成树就得到答案了。
这题略卡常，上个快读稳一点。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <deque>
#include <ctime>
#include <map>
#include <set>
#define ll long long
#define inf 0x3f3f3f3f
#define il inline
namespace io {
#define in(a) a = read()
#define out(a) write(a)
#define outn(a) out(a), putchar('\n')
#define I_int ll
inline I_int read() {
I_int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
char F[200];
inline void write(I_int x) {
if (x == 0) return (void) (putchar('0'));
I_int tmp = x > 0 ? x : -x;
if (x < 0) putchar('-');
int cnt = 0;
while (tmp > 0) {
F[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while (cnt > 0) putchar(F[--cnt]);
}
#undef I_int
}
using namespace io;
using namespace std;
#define N 8000010
int n, m, k, t, a[N], f[N];
struct edge {
int u, v, w;
}e[N];
bool operator < (edge a, edge b) {
return a.w < b.w;
}
int find(int x) {
if(f[x] == x) return x;
return f[x] = find(f[x]);
}
int main() {
in(n), in(m), in(k), in(t);
int cnt = 0;
for(int i = 1; i <= n; ++i) {
int x = read();
e[++cnt] = (edge) {i, n + 1, x};
}
++n;
for(int i = 1; i <= n; ++i) f[i] = i;
for(int i = 1; i <= k; ++i) {
int x = read();
e[++cnt] = (edge) {x, n, 0};
}
for(int i = 1; i <= m; ++i) {
int u = read(), v = read(), w = read();
e[++cnt] = (edge) {u, v, w};
}
sort(e+1,e+cnt+1);
ll ans = 0;
for(int i = 1; i <= cnt; ++i) {
int x = find(e[i].u), y = find(e[i].v);
if(x != y) {
f[y] = x;
ans += e[i].w;
}
}
if(ans > t) puts("No");
else puts("Yes");
// outn(ans);
}