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;
}