Source code for submission s1184

spider.cpp

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <queue>
  5. #include <cstring>
  6. using namespace std;
  7.  
  8. int total_length;
  9. bool connected[2001];
  10.  
  11. struct Edge
  12. {
  13. int v1,v2,l;
  14. Edge(int from,int to,int length)
  15. {
  16. v1=from;v2=to;l=length;
  17. }
  18. };
  19.  
  20. bool cmpE(const Edge &e1, const Edge &e2)
  21. {
  22. return e1.l < e2.l;
  23. }
  24.  
  25. vector<Edge> edges;
  26. vector<Edge> tree;
  27.  
  28. void print_edges(const vector<Edge> &edges)
  29. {
  30. for(int i = 0; i < edges.size(); i++)
  31. cout << edges[i].l << ',';
  32. cout << endl;
  33. }
  34.  
  35. void AddToG(const Edge &e)
  36. {
  37. tree.push_back(e);
  38. total_length += e.l;
  39. connected[e.v1] = true;
  40. connected[e.v2] = true;
  41. }
  42.  
  43. int FindEdge(int vertex)// najdu prvni hranu s timto uzlem k jiz pripojenymu uzlu
  44. {
  45. for(int i = 0, im = edges.size(); i < im; i++)
  46. {
  47. if(edges[i].v1 == vertex)
  48. {
  49. if(connected[edges[i].v2])
  50. return i;
  51. }
  52. else if(edges[i].v2 == vertex)
  53. {
  54. if(connected[edges[i].v1])
  55. return i;
  56. }
  57. }
  58. return -1;
  59. }
  60.  
  61. int main()
  62. {
  63. bool disconnected;
  64. int N,M,v1,v2,l;
  65. //
  66. while(1)
  67. {
  68. cin >> N >> M;
  69. if(cin.eof()) break;
  70. //
  71. tree.clear();
  72. edges.clear();
  73. memset(connected,0,2001);
  74. total_length = 0;
  75. disconnected = false;
  76. //
  77. for(int m = 0; m < M; m++)
  78. {
  79. cin >> v1 >> v2 >> l;
  80. edges.push_back(Edge(v1,v2,l));
  81. }
  82. sort(edges.begin(),edges.end(),cmpE);
  83. //
  84. AddToG(edges[edges.size()-1]);
  85. //
  86. for(int n = 1; n <= N; n++) // pro kazdy uzel
  87. {
  88. if(connected[n]) continue;
  89. // najdu prvni hranu s timto uzlem k pripojenymu uzlu
  90. int ei = FindEdge(n);
  91. if(ei < 0)
  92. {
  93. disconnected = true;
  94. break;
  95. }
  96. AddToG(edges[ei]);
  97. edges.erase(edges.begin()+ei);
  98. }
  99. //
  100. if(disconnected)
  101. cout << "disconnected\n";
  102. else
  103. cout << (total_length - (2*edges[edges.size()-1].l)) << '\n';
  104. }
  105. return 0;
  106. }