Tachibana Kanade Loves Review 牛客练习赛43

链接：https://ac.nowcoder.com/acm/contest/548/C

最小生成树

题目求能不能在t天内学完所有知识点，将每个知识点看成一个顶点，知识点间的联系看成边，这样问题就简化成了一个求最小生成树的问题了。但是还有一些点之间是没有联系的，即图是不连通的，所以我们需要引入一个节点0，将(0,i)这条边的权值定为Ti，这样图就联通了。另外就是条件k了，k个已经学习的知识点表明（0，ki）这条路径已经加入到最小生成树中，只需用并查集合并就好。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6 + 10;
const int M=7e6 + 10;//一共有m+n条边 不知道为什么6e6+10 就会超时 

int n,m,k;
long long t,sum=0;
int T;

struct Edge {
    int form,to,w;
    bool  operator < (const Edge x)const{
        return w<x.w;
    }
}e[M];
int cnt=0;

void addEdge(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].w=w;
    e[cnt].form=u;
}

int f[N];
int find(int x){
    return f[x]==x? x: f[x]=find(f[x]);
}

inline int read(){//快读 
    long long 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<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
int main(){
    
    n=read();m=read();k=read();t=read();
    //printf("%d %d %d %lld\n",n,m,k,t);
    f[0]=0;
    for(int i=1;i<=n;i++){
        f[i]=i;
        T=read();
        addEdge(0,i,T);//每个节点和虚拟节点0创建边 边权为点代价
    }
    int tmp;
    for(int i=1;i<=k;i++)
    {
        tmp=read();
        //printf("%d\n",tmp);
        f[tmp]=0;//已有节点和虚拟节点0连接 
    }
    int x,y,h;
    for(int i=0;i<m;i++){
        x=read();y=read();h=read();
        //printf("%d %d %d\n",x,y,h);
        addEdge(x,y,h);
    }
    
    sort(e+1,e+cnt+1);
    int ans=k;
    for(int i=1;i<=cnt;i++){
        x=find(e[i].form),y=find(e[i].to),h=e[i].w;
        if(x!=y){
            f[x]=y;
            sum+=h;
            ans++;
        }
        else continue;
        if(ans==n-1||sum>t) break;
    }
    //cout<<sum;
    if(sum>t)printf("No\n");
    else printf("Yes\n");
    return 0;
}