fork(1) download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <queue>
  7. #include <set>
  8. using namespace std;
  9. const int INF = 1000000000;
  10. const int MAX = 50000;
  11.  
  12. struct kruskal
  13. {
  14. 	int from;
  15. 	int to;
  16. 	int val;
  17. };
  18.  
  19. bool cmp(const kruskal& a, const kruskal& b)
  20. {
  21. 	return a.val < b.val;
  22. }
  23.  
  24. kruskal ks[MAX + 1];
  25. vector<pair<int, int> > adj[MAX + 1];
  26. int parent[MAX + 1];
  27. bool visit[MAX + 1];
  28. int dep[MAX + 1];
  29. int par[20][MAX + 1];
  30. int dist[20][MAX + 1];
  31. bool check[4 * MAX + 1];
  32.  
  33. int find(int x)
  34. {
  35. 	if (parent[x] == x)
  36. 		return x;
  37. 	else
  38. 		return parent[x] = find(parent[x]);
  39. }
  40.  
  41. bool merge(int x, int y)
  42. {
  43. 	x = find(x);
  44. 	y = find(y);
  45. 	if (x == y)
  46. 		return false;
  47. 	parent[x] = y;
  48. 	return true;
  49. }
  50.  
  51. void dfs(int x)
  52. {
  53. 	visit[x] = true;
  54. 	for (int i = 0; i < adj[x].size(); i++)
  55. 	{
  56. 		int next = adj[x][i].first;
  57. 		int cost = adj[x][i].second;
  58. 		if (!visit[next])
  59. 		{
  60. 			par[0][next] = x;
  61. 			dep[next] = dep[x] + 1;
  62. 			dist[0][next] = cost;
  63. 			dfs(next);
  64. 		}
  65. 	}
  66. }
  67.  
  68. int lca(int u, int v)
  69. {
  70. 	int ret = 0;
  71. 	if (dep[u] > dep[v])
  72. 		swap(u, v);
  73. 	for (int i = 19; i >= 0; i--)
  74. 	{
  75. 		int diff = dep[v] - dep[u];
  76. 		if (diff >= (1 << i))
  77. 		{
  78. 			ret = max(ret, dist[i][v]);
  79. 			v = par[i][v];
  80. 		}
  81. 	}
  82. 	if (u == v)
  83. 		return ret;
  84. 	for (int i = 19; i >= 0; i--)
  85. 	{
  86. 		if (par[i][u] != par[u][v])
  87. 		{
  88. 			ret = max(ret, max(dist[i][u], dist[i][v]));
  89. 			u = par[i][u];
  90. 			v = par[i][v];
  91. 		}
  92. 	}
  93. 	ret = max(ret, max(dist[0][u], dist[0][v]));
  94. 	return ret;
  95. }
  96.  
  97. int main()
  98. {
  99. 	int V, E;
  100. 	scanf("%d %d", &V, &E);
  101. 	for (int i = 0; i <= V; i++)
  102. 		parent[i] = i;
  103. 	for (int i = 0; i < E; i++)
  104. 	{
  105. 		int u, v, w;
  106. 		scanf("%d %d %d", &u, &v, &w);
  107. 		ks[i].from = u;
  108. 		ks[i].to = v;
  109. 		ks[i].val = w;
  110. 	}
  111. 	sort(ks, ks + E, cmp);
  112. 	long long sum = 0;
  113. 	int cnt = 0;
  114. 	bool flag = false;
  115. 	for (int i = 0; i < E; i++)
  116. 	{
  117. 		int u = ks[i].from;
  118. 		int v = ks[i].to;
  119. 		int w = ks[i].val;
  120. 		if (merge(u, v))
  121. 		{
  122. 			check[i] = true;
  123. 			adj[u].push_back(make_pair(v, w));
  124. 			adj[v].push_back(make_pair(u, w));
  125. 			sum += w;
  126. 			cnt++;
  127. 			if (cnt == V - 1)
  128. 			{
  129. 				flag = true;
  130. 				break;
  131. 			}
  132. 		}
  133. 	}
  134. 	if (!flag || E <= V - 1)
  135. 	{
  136. 		puts("-1");
  137. 		return 0;
  138. 	}
  139. 	dfs(1);
  140. 	for (int i = 1; i < 20; i++)
  141. 	{
  142. 		for (int j = 1; j <= V; j++)
  143. 		{
  144. 			par[i][j] = par[i - 1][par[i - 1][j]];
  145. 			dist[i][j] = max(dist[i - 1][j], dist[i - 1][par[i - 1][j]]);
  146. 		}
  147. 	}
  148. 	long long maxx = 0x3f3f3f3f3f3f3f3f;
  149. 	for (int i = 0; i < E; i++)
  150. 	{
  151. 		if (check[i])
  152. 			continue;
  153. 		int u = ks[i].from;
  154. 		int v = ks[i].to;
  155. 		int w = ks[i].val;
  156. 		int t = lca(u, v);
  157. 		if (t == w)
  158. 			continue;
  159. 		maxx = min(maxx, (long long)(sum - t + w));
  160. 	}
  161. 	if (maxx == 0x3f3f3f3f3f3f3f3f || maxx == sum)
  162. 		puts("-1");
  163. 	else
  164. 		printf("%lld\n", maxx);
  165. 	return 0;
  166. }
Success #stdin #stdout 0s 25440KB
comments (?)
stdin
copy 
7 12
1 2 8
1 3 5
2 3 10
2 4 2
2 5 18
3 4 3
3 6 16
4 5 12
4 6 30
4 7 14
5 7 4
6 7 26
stdout
copy 
44
https://ideone.com/DaRuTo
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!