题解 | #呜米喵想要成为爱抖露！#

我们读题可以发现
这道题其实就是 给出n个点 m条边
要求把所有点联通后 所用的边的权值和最小
我们在往下看 可以发现下面gachi只是把权值为质数的边权值变成0
所有我们只需要读入边的时候把权值为质数的边 权值替换成0
然后跑一遍最小生成树
只不过需要的质数范围大 需要线性素数筛
这题其实是个签到题.............

#include<bits/stdc++.h>
using namespace std;
struct bian { 
    long long int a, b, v;
}a[210000];
long long int n, m, bcj[210000], mn;
long long int ss[1100000] = { 0,2 }, sz;
long long int find(long long int fd) {
    return bcj[fd] == fd ? fd : bcj[fd] = find(bcj[fd]);
}
bool cmp(struct bian q, struct bian p) {
    return q.v < p.v;
}
bool hs[11000000] = { 1,1 };
long long int k,num,sum,fk;
int main() {
    //freopen("11.in", " r ", stdin);
    //freopen("11.out", " w ", stdout);
    cin >> n >> m>>k;
    for (long long int i = 0; i <= n; i++)
    {
        bcj[i] = i;
    }
    for (long long int i = 0; i < m; i++)
    {
        long long int  ab, bb, vq;
        cin >> ab >> bb >> vq;
        a[i].a = ab;
        a[i].b = bb;
        a[i].v = vq;
        fk=max(fk,vq);
    }
    for (long long int i = 2; i <= fk; i++)
    {
        if (hs[i] == false)
            ss[++sz] = i;
        for (long long int j = 1; j <= sz && i * ss[j] <= fk; j++)
        {
            if (i * ss[j] > fk)break;
            hs[ss[j] * i] = 1;
            if (i % ss[j] == 0)
            {
                break;
            }
        }
    }
    for (long long int i = 0; i < m; i++)
    {
        if (hs[a[i].v] == false)
        {
            a[i].v = 0;
        }
    }
    sort(a, a + m, cmp);
    for (long long int i = 0; i < m; i++)
    {
        long long int fa = find(a[i].a);
        long long int fb = find(a[i].b);
        if (fa != fb)
        {
            bcj[fb] = fa;
            num++;
            sum += a[i].v;
        }
        if (num == (n - 1)) {
            break;
        }
    }
    if (num == (n - 1)&&sum<k)
        cout << "wmmxycwdjdwdlnljbzwtskirakira";
    else
        cout << "wmmxycwdjdwdlnljbzwtsfljt";
    return 0;
}