Source code for submission s928

spider.cpp

  1. #include <stdio.h>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. struct Link {
  6. int nodeA;
  7. int nodeB;
  8. int len;
  9. };
  10.  
  11. bool comparathor(Link const & a, Link const & b)
  12. {
  13. return a.len < b.len;
  14. }
  15.  
  16.  
  17. Link maxlink;
  18. int linkcount;
  19. int nodecount;
  20. int * nodes;
  21. int components;
  22. std::vector<Link> links;
  23. long long fullSize;
  24.  
  25. int component(int node)
  26. {
  27. if (*(nodes + node) == node)
  28. return node;
  29. else
  30. {
  31. int cmp = component(*(nodes + node));
  32. *(nodes + node) = cmp;
  33. return cmp;
  34. }
  35. }
  36.  
  37. void setComponent(int node, int component)
  38. {
  39. if (*(nodes + node) == node)
  40. *(nodes + node) = component;
  41. else
  42. {
  43. setComponent(*(nodes + node),component);
  44. *(nodes + node) = component;
  45. }
  46. }
  47.  
  48. int main (int argc, char * argv[])
  49. {
  50. nodes = 0;
  51. // full run
  52. while (scanf("%d %d",&nodecount,&linkcount)==2)
  53. {
  54. // init
  55. maxlink.len = 0;
  56. components = nodecount;
  57. links.clear();
  58. delete[] nodes;
  59. nodes = new int[nodecount];
  60. for (int i(0);i<nodecount;++i)
  61. *(nodes+i) = i;
  62. fullSize = 0;
  63.  
  64. // links reading
  65. Link curLink;
  66. for (int i (0);i<linkcount;++i)
  67. {
  68. scanf("%d %d %d",&curLink.nodeA,&curLink.nodeB,&curLink.len);
  69. --curLink.nodeA;
  70. --curLink.nodeB;
  71. if (curLink.len > maxlink.len)
  72. maxlink = curLink;
  73. links.push_back(curLink);
  74. }
  75.  
  76. // SORT LINKS HERE
  77. sort(links.begin(),links.end(),comparathor);
  78.  
  79. // implicitly use maxlink
  80. *(nodes+maxlink.nodeA) = *(nodes+maxlink.nodeB);
  81. --components;
  82.  
  83. // find minimal kostra
  84. for (std::vector<Link>::const_iterator pnter(links.begin());pnter!=links.end();++pnter)
  85. {
  86. if (component(pnter->nodeA) != component(pnter->nodeB))
  87. {
  88. fullSize += pnter->len;
  89. setComponent(pnter->nodeA,*(nodes + pnter->nodeB));
  90. --components;
  91. }
  92. }
  93.  
  94. fullSize -= maxlink.len;
  95. if (components > 1)
  96. printf("disconnected\n");
  97. else
  98. printf("%lld\n",fullSize);
  99. }
  100. }
  101.