fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4.  
  5. int* addtown(int * seed, int x, int* path, int pathn)
  6. {
  7. 	int canadd = 0;
  8. 	for (int i = 0; i < pathn; i++)
  9. 	{
  10. 		for (int j = 1; j <= seed[0]; j++)
  11. 		{
  12. 			if (path[i*2] == seed[j] && path[i*2+1] == x)
  13. 			{	canadd = 1; break;	}
  14. 			if (path[i*2+1] == seed[j] && path[i*2] == x)
  15. 			{	canadd = 1; break;	}			
  16. 		}
  17. 		if (canadd) break;
  18. 	}
  19. 	if  (!canadd) return NULL;
  20. 	int *p = new int[seed[0] + 2];
  21. 	memcpy(p, seed, sizeof(int) * (seed[0] + 1));
  22. 	p[0]++;
  23. 	p[p[0] - 1] = x;
  24. }
  25.  
  26. int profit(int * seed)
  27. {
  28. 	if (seed[0] == 1) return 0;
  29. 	int max, min;
  30. 	max = min = seed[1];
  31. 	for (int i = 2; i <= seed[0]; i++)
  32. 	{
  33. 		if (max < seed[i]) max = seed[i];
  34. 		if (min > seed[i]) min = seed[i];
  35. 	}
  36. 	return max - min;
  37. }
  38.  
  39. int notin(int ** seed, int seedn, int x)
  40. {
  41. 	for (int i = 0; i < seedn; i++)
  42. 	{
  43. 		for (int j = 1; j <= seed[i][0]; j++)
  44. 			if (seed[i][j] == x) return 0;
  45. 	}
  46. 	return 1;
  47. }
  48.  
  49. int solve(int ** seed, int selectedn, int n, int mn, int* routes)
  50. {
  51. 	if (selectedn == n)
  52. 	{
  53. 		int sum = 0;
  54. 		for (int i = 0; i < mn; i++)
  55. 		{
  56. 			sum += profit(seed[i]);
  57. 		}
  58. 		return sum;
  59. 	}
  60. 	int max = -1;
  61. 	for (int i = 0; i < n; i++)
  62. 	{
  63. 		if (notin(seed, mn, i))
  64. 		{
  65. 			for (int j = 0; j < mn; j++)
  66. 			{
  67. 				int * seed1 = addtown(seed[j], i, routes, n - 1);
  68. 				if (seed1)
  69. 				{
  70. 					int maxsub = solve(seed, selectedn + 1, n, mn, routes);
  71. 					if (max < maxsub) max = maxsub;
  72. 				}
  73. 			}
  74. 		}
  75. 	}
  76. 	return max;
  77. }
  78.  
  79. int main() {
  80. 	int townsn;
  81. 	cin >> townsn;
  82. 	int* towns = new int[townsn];
  83. 	for (int i = 0; i < townsn; i++)
  84. 		cin >> towns[i];
  85. 	int* routes = new int[(townsn - 1) * 2];
  86. 	for (int i = 0; i < townsn - 1; i++)
  87. 	{
  88. 		int x, y;
  89. 		cin >> x >> y;
  90. 		routes[i*2] = x - 1;
  91. 		routes[i*2+1] = y - 1;
  92. 	}
  93. 	int k;
  94. 	cin >> k;
  95. 	int* mchs = new int[k];
  96. 	int ** seed = new int*[k];
  97. 	for (int i = 0; i < k; i++)
  98. 	{
  99. 		int x;
  100. 		cin >> x;
  101. 		mchs[i] = x - 1;
  102. 		seed[i] = new int[2];
  103. 		seed[i][0] = 1;
  104. 		seed[i][1] = x - 1;
  105. 	}
  106. 	int result = solve(seed, k, townsn, k, routes);
  107. 	cout << result << endl;
  108. 	return 0;
  109. }
Runtime error #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
12
3 1 2 3 5 6 7 2 2 4 10 11
1 2
1 3
4 2
5 2
3 6
6 7
6 8
6 9
8 10
9 11
9 12
5
3 8 4 11 12
stdout
copy 
Standard output is empty
https://ideone.com/B5Btca
language:
C++ (gcc 8.3)
created:
4 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!