出题人题解 | #Tachibana Kanade Loves Review#

原题解链接： https://ac.nowcoder.com/discuss/173818

简单的图论题。

首先，我们考虑最简单的情况，即$k=0k=0$。然后，为了判定答案是否合法，我们考虑求出学完所有知识点的最小用时。考虑到一个知识点$yy$只能被下列两种途径学会：

单独学习这一个知识点，耗时$T_{y}T\_y$ ​

从某个已经学会的知识点$xx$中学习得来，耗时$H_{xy}H\_\{xy\}$ ​

如果我们新建一个“虚拟知识点”$GG$，并假设它刚开始便已经学会。那么，我们可以将第一种方案转化为第二种方案，即$H_{Gy}H\_\{Gy\}$ 。而学会所有知识点，本质上就是将所有知识点联通，即求出原图的最小生成树即可。

下面，我们再考虑$k>0k\; >\; 0$。我们可以再次使用虚拟节点$GG$，如果这个知识点初始时就已经学过，则只需要将其向虚拟节点$GG$连接一条边权为0的边，即可达到要求。

时间复杂度$O((m+k)\log (m+k))O((m+k)\; \backslash log\; (m+k))$。

当然这时肯定会有人怒斥出题人“你的题怎么卡常啊”。

$stdstd$写道这一步已经通过了，但考虑到一些选手可能没有写读入优化的习惯，因此我们可以进一步优化。

1. 注意到每条边的边权在$10^{3}10^3$以内，因此我们可以将$KruskalKruskal$算法中的快速排序改为计数排序，砍掉排序的一个$loglog$，
2. 结合并查集的路径压缩与启发式合并，可以$O((m+k)\alpha (m+k))O((m\; +\; k)\; \backslash alpha(m+k))$解决此题。
3. 注意到如果在计算某一条边时，你所消耗的时间已经超过了 $TT$，那么可以直接跳过。
4. 同理，注意到 $t⩽10^{18}t\; \backslash leqslant\; 10^\{18\}$ ，但是如果$tt$超过了$10^3\times 10^3\; \backslash times$边数， 答案一定为$YesYes$

实际只需要第$22$个优化，便可以轻松通过此题。

#include <bits/stdc++.h>

constexpr int N = 1e7 + 50;

int n, g, k, t, m, f[N], size[N];
long long mincost = 0;
struct Edge
{
    int u, v, w;
    inline bool operator< (const Edge e) const { return w < e.w; } 
} e[N];

inline char nc()
{
    static char buf[10000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 10000000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int read()
{
    int res = 0;
    char ch;
    do ch = nc(); while (ch < 48 || ch > 57);
    do res = res * 10 + ch - 48, ch = nc(); while (ch >= 48 && ch <= 57);
    return res;
}

inline void add(int u, int v, int w)
{
    e[++m].u = u;
    e[m].v   = v;
    e[m].w   = w;	
}

inline void find(int &x)
{
	while (x != f[x])
		x = f[x] = f[f[x]];
}
inline void merge(int x, int y)
{
	if (size[x] > size[y]) std::swap(x, y);
	f[x] = y;
	size[y] += size[x];
}

inline void kruskal()
{
    std::sort(e + 1, e + m + 1);
    for (int i = 1; i <= m; ++i)
    {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        find(u); find(v);
        if (u != v)
        {
            mincost += w;
            merge(u, v);
        }
        if (mincost > t) return;
    }
}

int main()
{
    n = read() + 1, g = read(), k = read(), t = read();
    for (int i = 1; i < n; ++i)
    {
    	f[i] = i;
    	size[i] = 1;
        int T = read();
        assert(T <= 1000);
        add(i, n, T);
    }
    f[n] = n; size[n] = 1;
    for (int i = 1; i <= k; ++i)
    	add(read(), n, 0);
	for (int i = 1; i <= g; ++i)
	{
		int u = read(), v = read(), w = read();
		add(u, v, w); 
	}
    kruskal();
    puts(mincost <= t ? "Yes" : "No");
    return 0;
}