牛客练习赛43C Tachibana Kanade Loves Review

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

题目大意：

　　略

分析：

　　这是一道求最小生成树的模板题，对于给定的知识点，可以假想一个已经学会的 0 号知识点，那么所有知识点之间就都可以用带权值的边关联起来了，如果某个知识点已经学完，那么从 0 号知识点学习那个知识点的边权值就设为 0 即可。

　　PS:我当初做的时候数据并不强，现在提交过去AC的代码居然Wa，优化了一下才过（不要用结构体，尽量避免函数调用）。

代码如下：

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 #define rep(i,n) for (int i = 0; i < (n); ++i)
  5 #define For(i,s,t) for (int i = (s); i <= (t); ++i)
  6 #define rFor(i,t,s) for (int i = (t); i >= (s); --i)
  7 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
  8 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)
  9 
 10 #define pr(x) cout << #x << " = " << x << "  "
 11 #define prln(x) cout << #x << " = " << x << endl
 12 
 13 #define ALL(x) x.begin(),x.end()
 14 #define INS(x) inserter(x,x.begin())
 15 
 16 #define ms0(a) memset(a,0,sizeof(a))
 17 #define msI(a) memset(a,inf,sizeof(a))
 18 
 19 #define pii pair<int,int> 
 20 #define piii pair<pair<int,int>,int> 
 21 #define mp make_pair
 22 #define pb push_back
 23 #define fi first
 24 #define se second
 25 
 26 typedef long long LL;
 27 const int maxN = 1e6 + 7;
 28 
 29 inline int gc(){
 30     static const int BUF = 1e7;
 31     static char buf[BUF], *bg = buf + BUF, *ed = bg;
 32     
 33     if(bg == ed) fread(bg = buf, 1, BUF, stdin);
 34     return *bg++;
 35 } 
 36 
 37 inline int ri(){
 38     int x = 0, f = 1, c = gc();
 39     for(; c<48||c>57; f = c=='-'?-1:f, c=gc());
 40     for(; c>47&&c<58; x = x*10 + c - 48, c=gc());
 41     return x*f;
 42 }
 43 
 44 struct Vertex;
 45 struct Edge;
 46 
 47 int n, m, k, ans; 
 48 LL t;
 49 
 50 int f[maxN], sz[maxN];
 51 
 52 inline void Find(int &x){
 53     while (x != f[x]) x = f[x] = f[f[x]];
 54 } 
 55 
 56 inline void Union(int x, int y){
 57     if (sz[x] > sz[y]) swap(x, y);
 58     f[x] = y;
 59 }
 60 
 61 
 62 struct Edge{
 63     int weight;
 64     int from, to;
 65     
 66     Edge(){}
 67     
 68     Edge(int w, int f, int t) : weight(w), from(f), to(t){}
 69     bool operator < (const Edge &x) const {
 70         return weight < x.weight;
 71     }
 72     
 73     void print() const{
 74         printf("Edge:
");
 75         printf("    ");prln(weight);
 76         printf("    ");prln(from);
 77         printf("    ");prln(to);
 78     }
 79 };
 80 
 81 Edge E[maxN*10];
 82 int elen = 0;
 83 
 84 // 返回值为最小生成树的权值总和 
 85 inline int kruskal(int n){
 86     rep(i, n+1){
 87         f[i] = i;
 88     }
 89 
 90     int cnt = 0, ret = 0;
 91 
 92     sort(E + 1, E + elen + 1);
 93 
 94     For(i, 1, elen){
 95         int x = E[i].from, y = E[i].to;
 96 
 97         Find(x);
 98         Find(y);
 99         if(x == y) continue;
100         else {
101             Union(x, y);
102             ++cnt;
103             ret += E[i].weight;
104             if(ret > t) return ret;
105         }
106     }
107     return ret;
108 }
109 
110 int main(){
111     scanf("%d%d%d%d", &n, &m, &k, &t);
112     // 假想一个0号知识点，并且已经会了
113     For(i, 1, n) E[++elen] = Edge(ri(), 0, i);
114     For(i, 1, k) E[ri()].weight = 0;
115     For(i, 1, m){
116         int x = ri(), y = ri(), h = ri();
117         E[++elen] = Edge(h, x, y);
118     }
119     // 求最小生成树
120     ans = kruskal(n);
121     
122     if(ans > t) printf("No
");
123     else printf("Yes
");
124     return 0;
125 }

View Code