kananasgarli90

Minimal çəkili ağac

Sep 25th, 2020
845
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define INF 1000000
  4. int color[101];
  5. int adj[101][101];
  6. set<int>s;
  7. int main()
  8. {
  9.     int n, m, u, v, w, a, b, mst = 0;
  10.     cin>>n>>m;
  11.     while(m--){
  12.         cin>>u>>v>>w;
  13.         adj[u][v] = adj[v][u] = w;
  14.     }
  15.     color[1] = 1;
  16.     s.insert(1);
  17.     while(s.size() != n){
  18.         int min_weight = INF;
  19.         for(auto i = s.begin(); i != s.end(); i++){
  20.             a = *i;
  21.             for(int j = 1; j <= n; j++){
  22.                 if(adj[a][j] > 0 && color[j] == 0 && adj[a][j] < min_weight){
  23.                     min_weight = adj[a][j];
  24.                     b = j;
  25.                 }
  26.             }
  27.         }
  28.         color[b] = 1;
  29.         s.insert(b);
  30.         mst += min_weight;
  31.     }
  32.  
  33.     cout<<mst<<endl;
  34. }
  35.  
  36.  
  37.  
RAW Paste Data