Source code for submission s1023

fr.cpp

  1. #include <cstdio>
  2. #include <queue>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <vector>
  6. using namespace std;
  7.  
  8. int N, C;
  9.  
  10. struct Dvojice
  11. {
  12. int vrchol;
  13. int cena;
  14. };
  15.  
  16. struct Prvek
  17. {
  18. int index;
  19. bool existuje;
  20. bool koren;
  21. vector<Dvojice> sousede;
  22. int synu;
  23. int soucet;
  24. } pole[1005];
  25.  
  26. int main()
  27. {
  28. int a,b,c;
  29. Prvek prvek;
  30. Dvojice dvojice;
  31.  
  32. while(scanf("%d", &N) != EOF)
  33. {
  34. //printf("Nacitani:\n");
  35. scanf("%d", &C);
  36.  
  37. for(int i=1; i<=N; i++)
  38. {
  39. pole[i].index = i;
  40. pole[i].existuje = true;
  41. pole[i].koren = false;
  42. pole[i].soucet = 0;
  43. pole[i].synu = 0;
  44. /**
  45.   while(pole[i].sousede.size() > 0)
  46.   pole[i].sousede.pop_back();
  47.   **/
  48. pole[i].sousede.clear();
  49. }
  50. for(int i=1; i<=N-1; i++)
  51. {
  52. //printf("%d-ty:\n", i);
  53. scanf("%d%d%d", &a, &b, &c);
  54. /**
  55.   pole[b].otec = a;
  56.   pole[b].value = c;
  57.   pole[b].synu = 0;
  58.   pole[a].synu++;
  59.   pole[b].soucet = 0;
  60.   **/
  61.  
  62. dvojice.vrchol = b;
  63. dvojice.cena = c;
  64. pole[a].sousede.push_back(dvojice);
  65. pole[a].synu++;
  66. dvojice.vrchol = a;
  67. pole[b].sousede.push_back(dvojice);
  68. pole[b].synu++;
  69. }
  70. pole[C].koren = true;
  71.  
  72. /**
  73.   for(int i=1; i<=N; i++)
  74.   {
  75.   printf("%d) index=%d exist=%d koren=%d synu=%d souc=%d ... ", i, pole[i].index, pole[i].existuje, pole[i].koren, pole[i].synu, pole[i].soucet);
  76.   for(int j=0; j<pole[i].sousede.size(); j++)
  77.   {
  78.   printf("[%d,%d] ", pole[i].sousede.at(j).vrchol, pole[i].sousede.at(j).cena);
  79.   }
  80.   printf("\n");
  81.   }
  82. **/
  83.  
  84.  
  85. queue<Prvek> fronta;
  86. for(int i=1; i<=N; i++)
  87. {
  88. if(pole[i].synu == 1) // 1 soused
  89. {
  90. pole[i].soucet = 123456789;
  91. fronta.push(pole[i]);
  92. //printf("frona.push(%d)\n", i);
  93. }
  94. }
  95.  
  96. while(!fronta.empty())
  97. {
  98. prvek = fronta.front();
  99. fronta.pop();
  100.  
  101. /**
  102.   printf("\n\n\n\n\nFRONTA:\n");
  103.   printf("PRVEK[%d]\n", prvek.index);
  104.   for(int i=1; i<=N; i++)
  105.   {
  106.   printf("%d) index=%d exist=%d koren=%d synu=%d souc=%d ... ", i, pole[i].index, pole[i].existuje, pole[i].koren, pole[i].synu, pole[i].soucet);
  107.   for(int j=0; j<pole[i].sousede.size(); j++)
  108.   {
  109.   printf("[%d,%d] ", pole[i].sousede.at(j).vrchol, pole[i].sousede.at(j).cena);
  110.   }
  111.   printf("\n");
  112.   }
  113.   printf("\n");
  114. **/
  115.  
  116.  
  117. if(prvek.koren == false) // ne centralni prvek
  118. {
  119. for(int i=0; i<prvek.sousede.size(); i++)
  120. {
  121. if(pole[prvek.sousede.at(i).vrchol].existuje == true)
  122. {
  123. dvojice = prvek.sousede.at(i);
  124. break;
  125. }
  126. }
  127. //printf("pole[%d]->otec: [%d,%d]\n", prvek.index, dvojice.vrchol, dvojice.cena);
  128. if(prvek.soucet <= dvojice.cena)
  129. {
  130. pole[dvojice.vrchol].soucet += prvek.soucet;
  131. //printf("1) pole[%d].soucet += %d\n", dvojice.vrchol, prvek.soucet);
  132. }
  133. else
  134. {
  135. pole[dvojice.vrchol].soucet += dvojice.cena;
  136. //printf("2) pole[%d].soucet += %d\n", dvojice.vrchol, dvojice.cena);
  137. }
  138. pole[prvek.index].existuje = false;
  139. pole[dvojice.vrchol].synu--;
  140. if(pole[dvojice.vrchol].synu == 1)
  141. fronta.push(pole[dvojice.vrchol]); // posledni prikaz bloku!!
  142. }
  143. else
  144. {
  145. printf("%d\n", pole[prvek.index].soucet); // VYSLEDEK
  146. break;
  147. }
  148.  
  149. /**
  150.   printf("KONEC:\n");
  151.   for(int i=1; i<=N; i++)
  152.   {
  153.   printf("%d) index=%d exist=%d koren=%d synu=%d souc=%d ... ", i, pole[i].index, pole[i].existuje, pole[i].koren, pole[i].synu, pole[i].soucet);
  154.   for(int j=0; j<pole[i].sousede.size(); j++)
  155.   {
  156.   printf("[%d,%d] ", pole[i].sousede.at(j).vrchol, pole[i].sousede.at(j).cena);
  157.   }
  158.   printf("\n");
  159.   }
  160.   **/
  161. }
  162.  
  163. //printf("Konec_Vypoctu\n");
  164. // ṕro jistotu
  165. while(!fronta.empty())
  166. fronta.pop();
  167.  
  168. }
  169.  
  170. return 0;
  171. }
  172.