牛客网练习赛43-C（图论）

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

题意：有n个知识点，学会每个知识点花T[i]，已经学会了其中k个知识点，有m组关系，t1,t2,t3，表示学会t2/t3之后学另一个知识点需要花H[i]，时限为t，问能否在时限之前学完所有的知识点。

思路：将n个知识点编号为1..n，然后构造一个虚拟的知识点0，该知识点已经学会，且该知识点到其它知识点的距离分别是T[i]，若知识点i已经学会了，则0到i的距离为0，m组关系对应m条边，这样就简化成了求最小生成树的问题了。将边按权值升序排序，利用kruskal算法就行了。但要注意的是题目的输入量十分大，达到了10的7次方，所以需要读入优化，不然会超时。

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3  
 4 inline int read(){
 5     int x=0,f=0;char ch=0;
 6     while(!isdigit(ch)){f|=ch=='-';ch=getchar();}
 7     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
 8     return f?-x:x;
 9 }
10 
11 inline long long LLread(){
12     long long x=0;int f=0;char ch=0;
13     while(!isdigit(ch)){f|=ch=='-';ch=getchar();}
14     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
15     return f?-x:x;
16 }
17 
18 struct node{
19     int u,v,w;
20 }a[7000005];
21 
22 bool cmp(node x,node y){
23     return x.w<y.w;
24 }
25 
26 typedef long long LL;
27 int n,m,k,t,cnt,p,root[1000005];
28 LL sum;
29 
30 void add(int x,int y,int z){
31     a[++p].u=x;
32     a[p].v=y;
33     a[p].w=z;
34 }
35 
36 int getr(int kk){
37     if(root[kk]==kk) return kk;
38     else return root[kk]=getr(root[kk]);
39 }
40 
41 int main(){
42     n=read(),m=read(),k=read(),t=LLread();
43     for(int i=0;i<=n;++i)
44         root[i]=i;
45     for(int i=1;i<=n;++i){
46         int tmp=read();
47         add(0,i,tmp);
48     }
49     for(int i=1;i<=k;++i){
50         int tmp=read();
51         add(0,tmp,0);
52     }
53     for(int i=1;i<=m;++i){
54         int t1=read(),t2=read(),t3=read();
55         add(t1,t2,t3);
56     }
57     sort(a+1,a+p+1,cmp);
58     for(int i=1;i<=p;++i){
59         int x=a[i].u,y=a[i].v,z=a[i].w,rx,ry;
60         rx=getr(x),ry=getr(y);
61         if(rx!=ry){
62             ++cnt;
63             sum+=z;
64             root[ry]=rx;
65         }
66         if(cnt==n||sum>t) break;
67     }
68     if(cnt==n&&sum<=t) printf("Yes
");
69     else printf("No
");
70     return 0;
71 }

牛客网练习赛43-C（图论）

相关推荐