xeritt

Оптимизация транспортной системы Марса

Oct 15th, 2019
106
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2. Шёл 2058 год. Колонии первых поселенцев уже высадились на Марсе и стали его обживать.  
  3. Для нормального функционирования шатл-станция нуждается в постоянном питании от энергетической сети. Чтобы запитать станцию нужно либо построить урановый ядерный генератор энергии внутри самой станции, либо проложить кабель до другой (уже запитанной) шатл-станции. Стоимость строительства генератора внутри разных шатл-станций может отличаться. Проведение кабеля между шатл-станциями также варьируется по стоимости и не всегда возможно. Кабельное соединение является двунаправленным.  
  4. Задача состоит в том, чтобы организовать эффективное (с минимальной стоимостью) питание всех шатл-станций.  
  5. На вход программа получает общее число шатл-станций, стоимости строительства генераторов для каждой шатл-станции и описания всех возможных кабелей между шатл-станциями (номера соединяемых станций и стоимость прокладки кабеля).
  6. Формат ввода
  7. Первая строка содержит одно целое неотрицательное число шатл-станций N≤1000.  
  8. Вторая строка содержит N чисел, задающих стоимости строительства генератора внутри соответствующей станции.  
  9. Третья строка содержит одно целое неотрицательное число возможных кабелей K≤100000 между шатл-станциями.  
  10. Последующие K строк (начиная с четвёртой) содержат описание одного кабеля - три целых неотрицательных числа: номер первой станции, номер второй станции и стоимость проведения.
  11. Формат вывода
  12. Одно целое число - минимальная стоимость питания всех шатл-станций для заднной конфигурации.
  13. Windows:
  14.     gcc main.cpp -std=gnu++14 -lstdc++ -o main
  15. Linux:
  16.     g++ -std=gnu++14 -Wall main.cpp -o main
  17. **/
  18. #include <iostream>
  19. #include <string>
  20. #include <vector>
  21. #include <sstream>
  22.  
  23. using namespace std;
  24. class Cable{
  25.     public:
  26.         int start, end, w;
  27.         Cable(int start, int end, int w) : start(start), end(end), w(w){}
  28. };
  29. class Base{
  30.     public:
  31.         int w;
  32.         bool connect = false;
  33.         Base(int w):w(w){}
  34.         Base(int w, bool connect):w(w), connect(connect){}
  35. };
  36. class Mars{
  37.     public:
  38.         int cur_cab = 0;
  39.         int max(vector<Base> base){
  40.             int m = 0;
  41.             for(unsigned int i=0; i<base.size(); i++){
  42.                 if (base[m].w < base[i].w) m = i;
  43.             }
  44.             return m;
  45.         }
  46.         int min(vector<Base> base){
  47.             int m = -1;
  48.             for(unsigned int i=0; i<base.size(); i++){
  49.                 if (base[i].connect==false){
  50.                     if (m==-1){
  51.                         m = i;
  52.                         continue;
  53.                     }
  54.                     if (base[m].w > base[i].w) {
  55.                         m = i;
  56.                     }  
  57.                 }
  58.             }
  59.             return m;
  60.         }
  61.         int getNotConnected(vector<Base> &base, vector<Cable> &cab, int base_i){
  62.             if (!base[base_i].connect) return -1;
  63.             for (unsigned int i = 0; i<cab.size(); i++){
  64.                 cur_cab = i;
  65.                 if (cab[i].start == base_i && !base[cab[i].end].connect){
  66.                         if (base[cab[i].end].w > cab[i].w)
  67.                         return cab[i].end;
  68.                 }
  69.                
  70.                 if (cab[i].end == base_i && !base[cab[i].start].connect){
  71.                     if (base[cab[i].start].w > cab[i].w)
  72.                         return cab[i].start;
  73.                 }
  74.             }
  75.             return -1;
  76.         }
  77.         int getConnected(vector<Base> &base, vector<Cable> &cab, int base_i){
  78.             if (base[base_i].connect) return -1;
  79.             for (unsigned int i = 0; i<cab.size(); i++){
  80.                
  81.                 if (cab[i].start == base_i && base[cab[i].end].connect){
  82.                     if (base[cab[i].start].w > cab[i].w)
  83.                         return i;
  84.                 }
  85.                
  86.                 if (cab[i].end == base_i && base[cab[i].start].connect){
  87.                     if (base[cab[i].end].w > cab[i].w)
  88.                         return i;
  89.                 }
  90.             }
  91.             return -1;
  92.         }
  93.         int calculate(vector<Base> &base, vector<Cable> &cab){
  94.             int sum = 0, m = 0;
  95.             while ((m = min(base))>-1){
  96.                 if (m==-1)
  97.                     return -1;
  98.                
  99.                 int con = getConnected(base, cab, m);
  100.                 if (con>-1){
  101.                     base[m].connect = true;
  102.                     sum += cab[con].w;
  103.                     cout<<"Connect["<<m<<"] from cab["<<con<<"] cost="<<cab[con].w<<endl;
  104.                     continue;
  105.                 }
  106.                
  107.                 base[m].connect = true;
  108.                 sum += base[m].w;
  109.                 cout<<"Init gen["<<m<<"] cost="<<base[m].w<<endl;
  110.                 int i = 0;
  111.                 while ((i = getNotConnected(base, cab, m))>-1){
  112.                     base[i].connect = true;
  113.                     sum += cab[cur_cab].w;
  114.                     cout<<"Connect base["<<i<<"] from cab["<<cur_cab<<"] cost="<<cab[cur_cab].w<<endl;
  115.                 }
  116.             }
  117.             return sum;
  118.         }
  119. };
  120. void parseGen(const string& inpstr, vector<Base>& res){
  121.     istringstream iss(inpstr);
  122.     for(string str; iss >> str; ){
  123.         int w = stoi(str);
  124.         res.push_back(Base(w));
  125.         cout<<"["<<w<<"]";       
  126.     }    
  127.     cout<<endl;
  128. }  
  129. void parseCab(const string& inpstr, vector<Cable>& res){
  130.     istringstream iss(inpstr);
  131.     vector<int> buf;
  132.     for(string str; iss >> str; )
  133.         buf.push_back(stoi(str));
  134.     if (buf.size()<3){
  135.         cout<<"error cable ["<<inpstr<<"]"<<endl;
  136.     } else{
  137.         cout<<"cable ["<<buf[0]<<","<<buf[1]<<","<<buf[2]<<"]"<<endl;        
  138.         res.push_back(Cable(buf[0], buf[1], buf[2]));
  139.     }      
  140. }  
  141.  
  142.  
  143. int main(int argc, char **argv)
  144. {
  145.     int N;
  146.     cin>>N;
  147.     cin.ignore();
  148.    
  149.     string generatorCost;
  150.     getline(cin, generatorCost);
  151.  
  152.     vector<Base> gen;
  153.     parseGen(generatorCost, gen);
  154.     int K;
  155.     cin>>K;
  156.     cin.ignore();
  157.  
  158.     string cables;
  159.     vector<Cable> cab;
  160.     for (int i = 0; i<K; i++){
  161.         getline(cin, cables);
  162.         parseCab(cables, cab);
  163.     }  
  164.  
  165.     Mars mars;
  166.     cout<<"sum="<<mars.calculate(gen, cab)<<endl;
  167.     return 0;
  168. }
RAW Paste Data Copied