fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cstdio>
  4. #include <vector>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <map>
  8. #include <set>
  9. #include <unordered_map>
  10. #include <cstring>
  11. #include <string.h>
  12. #include <iomanip>
  13. #include <queue>
  14. #include <stack>
  15. #include <complex>
  16. #include <list>
  17. #include <chrono>
  18. #include <random>
  19. using namespace std;
  20.  
  21. typedef long long LL;
  22. typedef unsigned long long ULL;
  23. typedef pair<int,int> PII;
  24. typedef vector<int> VI;
  25.  
  26. #define ALL(V) V.begin(), V.end()
  27. #define SZ(V) (int)V.size()
  28. #define PB push_back
  29. #define MP make_pair
  30. #define FOR(i, a, b) for(int i = (a); i < (b); ++i)
  31. #define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
  32. #define FILL(A,value) memset(A,value,sizeof(A))
  33. #define f first
  34. #define s second
  35.  
  36. const int INF = 1000*1000*1000+47;
  37. const LL LINF = (LL)INF*INF;
  38. const int MAX = 2e5;
  39. const double EPS = 1e-9;
  40. const double PI = acos(-1.);
  41.  
  42. int n;
  43. pair<int , PII> e[200];
  44. VI g[4];
  45. vector<VI> comp;
  46. int used[4];
  47. void dfs(int u, int col)
  48. {
  49. 	used[u] = col;
  50. 	comp[col-1].PB(u);
  51. 	FOR(i,0,SZ(g[u]))
  52. 	{
  53. 		int v = g[u][i];
  54. 		if (!used[v])
  55. 		{
  56. 			dfs(v, col);
  57. 		}
  58. 	}
  59. }
  60. int ban = 0;
  61.  
  62. int f(VI x)
  63. {
  64. 	int nep = 0;
  65. 	int p = 0;
  66. 	FOR(i,0,x.size())
  67. 	{
  68. 		if (g[x[i]].size()%2 == 0)
  69. 		{
  70. 			p++;
  71. 		} else
  72. 		{
  73. 			nep++;
  74. 		}
  75. 	}
  76. 	int res = 0;
  77. 	FOR(i,0,n)
  78. 	{
  79. 		if (i == ban)
  80. 			continue;
  81. 		int xx = e[i].s.f;
  82. 		FOR(j,0,x.size())
  83. 		{
  84. 			if (x[j] == xx)
  85. 			{
  86. 				res+=e[i].f;
  87. 				break;
  88. 			}
  89. 		}
  90. 	}
  91. 	if (nep == 4)
  92. 	{
  93. 		res=-INF;
  94. 	}
  95. 	return res;
  96. }
  97.  
  98.  
  99. int main()
  100. {
  101. 	ios_base::sync_with_stdio(0);
  102. 	//freopen("In.txt", "r", stdin);
  103. 	cin >> n;
  104. 	FOR(i,0,n)
  105. 	{
  106. 		int x,y,z;
  107. 		cin >> x >> y >> z;
  108. 		x--; z--;
  109. 		//g[x].PB(z);
  110. 		//g[z].PB(x);
  111. 		e[i] = MP(y, MP(x,z));
  112. 	}
  113. 	int ans = 0;
  114. 	FOR(i,-1,n)
  115. 	{
  116. 		ban = i;
  117. 		FOR(i,0,4)
  118. 			g[i].clear();
  119. 		FOR(i,0,n)
  120. 		{
  121. 			if (i == ban)
  122. 				continue;
  123. 			g[e[i].s.f].PB(e[i].s.s);
  124. 			g[e[i].s.s].PB(e[i].s.f);
  125. 		}
  126. 		comp.clear();
  127. 		FILL(used, 0);
  128. 		int c = 1;
  129. 		FOR(i,0,4)
  130. 		{
  131. 			if (used[i])
  132. 				continue;
  133. 			comp.PB(VI());
  134. 			dfs(i, c);
  135. 			c++;
  136. 		}
  137. 		FOR(i,0,comp.size())
  138. 		{
  139. 			ans = max(ans, f(comp[i]));
  140. 		}
  141. 	}
  142. 	cout << ans << endl;
  143.  
  144. 	return 0;
  145.  
  146. }
  147.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/dZbEb2
language:
C++ (gcc 8.3)
created:
5 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!