fork download
copy 
  1. /// n < k  -> cout << -1
  2.  
  3.  
  4. /// Author : Nguyễn Thái Sơn - K18 - KHMT - UIT
  5. /// Training ICPC 2024
  6.  
  7. #include<bits/stdc++.h>
  8.  
  9. /// #pragma GCC optimize("O3,unroll-loops")
  10. /// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  11.  
  12. #define fi first
  13. #define se second
  14. #define TASK "test"
  15. #define pb push_back
  16. #define EL cout << endl
  17. #define Ti20_ntson int main()
  18. #define in(x) cout << x << endl
  19. #define all(x) (x).begin(),(x).end()
  20. #define getbit(x, i) (((x) >> (i)) & 1)
  21. #define cntbit(x) __builtin_popcount(x)
  22. #define FOR(i,l,r) for (int i = l; i <= r; i++)
  23. #define FORD(i,l,r) for (int i = l; i >= r; i--)
  24. #define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl
  25.  
  26. using namespace std;
  27.  
  28. typedef long long ll;
  29. typedef vector<int> vi;
  30. typedef pair<int,int> vii;
  31. typedef unsigned long long ull;
  32. typedef vector<vector<int>> vvi;
  33. int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
  34.  
  35. const int N = 5e5 + 5;
  36. const int oo = INT_MAX;
  37. const int mod = 1e9 + 7;
  38. const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
  39. const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  40.  
  41. int n, a[N], m, k, Color[N];
  42. tuple<int, int, int> Edge[N];
  43.  
  44. ll Ans = 0;
  45.  
  46.  
  47. /// [1, 2, 3, ..., k]
  48.  
  49.  
  50. /// Color = 0 co the thay doi tuy y
  51.  
  52. /// Color[i] = 0 -> Color[i] > k
  53.  
  54. /// De no khong anh huong toi mau da to ( 1 -> k)
  55.  
  56.  
  57.  
  58. inline void Read_Input() {
  59.     cin >> n >> m >> k;
  60.  
  61.     int num = k;
  62.  
  63.     FOR(i, 1, n) {
  64.         cin >> Color[i];
  65.         if (Color[i] == 0) Color[i] = ++num;
  66.     }
  67.  
  68.     if (n < k) {
  69.         cout << -1;
  70.         exit(0);
  71.     }
  72.  
  73.     FOR(i, 1, m) {
  74.         int u, v, w;
  75.         cin >> u >> v >> w;
  76.         Edge[i] = {w, u, v};
  77.     }
  78.  
  79.     sort(Edge + 1, Edge + m + 1);
  80.  
  81. }
  82.  
  83. struct DSU {
  84.     vector<int> par;
  85.  
  86.     void sz(int n) {
  87.         par.resize(n + 5, -1);
  88.     }
  89.  
  90.     int Find(int u) {
  91.         if (par[u] < 0) return u;
  92.         par[u] = Find(par[u]);
  93.         return par[u];
  94.     }
  95.  
  96.     bool Merge(int x, int y) {
  97.         x = Find(x);
  98.         y = Find(y);
  99.         if (x == y) return 0;
  100.         if (par[x] > par[y])
  101.             swap(x, y);
  102.         par[x] += par[y];
  103.         par[y] = x;
  104.         return 1;
  105.     }
  106. }d;
  107.  
  108. inline void Solve() {
  109.     d.sz(k + n);
  110.     /// Color[i] = 0  -> Đỉnh i chưa được tô màu
  111.  
  112.     /// Color[i] > 0  -> Đinh i có màu sẵn rồi và ko cần thiết phải quan tâm
  113.  
  114.     /// cnt == k - 1 dung lai qua trinh tim cay khung k mau
  115.  
  116.  
  117.     int cnt = 0;
  118.  
  119.     FOR(i, 1, m) {
  120.  
  121.         auto[w, u, v] = Edge[i];
  122.  
  123.  
  124.         if (Color[u] && Color[v]) {
  125.  
  126.             /// mau sac 2 dinh u va v la co dinh
  127.  
  128.             if (d.Merge(Color[u], Color[v]) == true) {
  129.  
  130.                 /// Canh nay chac chan tao ra cay khung mau
  131.  
  132.                 Ans += w;
  133.  
  134.                 cnt++;
  135.             }
  136.  
  137.         }
  138.  
  139.             /// k - 1 cạnh sao cho nó hợp lý
  140.  
  141.             /// hợp lý khi và chỉ khi các thằng cùng mau sẽ không nối tới nhau
  142.  
  143.             /// thích màu nào cũng được cho nên vấn đề mà trùng màu sẽ không bao giờ xảy ra
  144.  
  145.             /// TH nay ta luon co the Merge(u -> v) mà không cần quan tâm tính đúng sai của màu
  146.  
  147.  
  148.  
  149.         if (cnt == k - 1) {
  150.             cout << Ans;
  151.             return;
  152.         }
  153.     }
  154.  
  155.     cout << -1;
  156.  
  157. }
  158.  
  159. Ti20_ntson {
  160. //    freopen(TASK".INP","r",stdin);
  161. //    freopen(TASK".OUT","w",stdout);
  162.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  163.     int T = 1;
  164. //    cin >> T;
  165.     while (T -- ) {
  166.         Read_Input();
  167.         Solve();
  168.     }
  169. }
  170.  
  171.  
  172.  
  173.  
Success #stdin #stdout 0s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/Hb7NOI
language:
C++14 (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!