Advertisement
Guest User

Untitled

a guest
Aug 21st, 2017
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.85 KB | None | 0 0
  1. #include <bits//stdc++.h>
  2. using namespace std;
  3.  
  4. const int inf = 16843009;
  5.  
  6. int par[1005], taken[1005], idx;
  7.  
  8. struct edge
  9. {
  10. int u, v, w;
  11.  
  12. edge(int u, int v, int w): u(u), v(v), w(w) {}
  13.  
  14. bool operator<(const edge &p)const
  15. {
  16. return w<p.w;
  17. }
  18. };
  19.  
  20. void makeset(int n)
  21. {
  22. for(int i = 0; i <n; i++) par[i] = i;
  23. }
  24.  
  25. int find_par(int n)
  26. {
  27. if (par[n]==n) return n;
  28.  
  29. par[n]=find_par(par[n]);
  30.  
  31. return par[n];
  32. }
  33.  
  34. vector<edge> E;
  35.  
  36. int kruskal(int n)
  37. {
  38.  
  39. sort(E.begin(), E.end());
  40.  
  41. makeset(n);
  42.  
  43. int sum = 0;
  44.  
  45. idx = 0;
  46.  
  47. for(int i = 0; i < E.size(); i++)
  48. {
  49. int u = find_par(E[i].u);
  50.  
  51. int v = find_par(E[i].v);
  52.  
  53. if(u != v)
  54. {
  55. par[u] = v;
  56.  
  57. taken[idx++] = i;
  58.  
  59. sum += E[i].w;
  60.  
  61. if(idx == n-1) break;
  62. }
  63. }
  64.  
  65. return sum;
  66.  
  67. }
  68.  
  69. int main()
  70. {
  71. int n, m, u, v, w, mini, cnt, sum;
  72.  
  73. cin>>n>>m;
  74.  
  75. E.clear();
  76.  
  77. memset(taken, 0, sizeof(taken));
  78.  
  79. for(int i = 0; i < m; i++)
  80. {
  81. cin>>u>>v>>w;
  82.  
  83. E.push_back(edge(u, v, w));
  84. }
  85.  
  86. int res = kruskal(n);
  87.  
  88. mini = inf;
  89.  
  90. for(int j=0; j<idx; j++)
  91. {
  92. makeset(n);
  93.  
  94. cnt=0;
  95. sum=0;
  96.  
  97. for(int i = 0; i < E.size(); i++)
  98. {
  99. if(taken[j] != i)
  100. {
  101. int u = find_par(E[i].u);
  102.  
  103. int v = find_par(E[i].v);
  104.  
  105. if(u!=v)
  106. {
  107. par[u] = v;
  108. cnt++;
  109. sum += E[i].w;
  110.  
  111. if(cnt==n-1) break;
  112. }
  113. }
  114. }
  115.  
  116. if(cnt == n-1) mini = min(mini, sum);
  117.  
  118. }
  119.  
  120. if(mini == inf) puts("No Second Best MST");
  121.  
  122. else printf("%d\n", mini);
  123.  
  124. return 0;
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement