fork(2) download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <map>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <ctime>
  8. #include <cstdlib>
  9. #include <cstdio>
  10. #include <utility>
  11. #include <iomanip>
  12. #include <assert.h>
  13. #define MP make_pair
  14. #define PB push_back
  15. #define int long long
  16. #define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
  17. #define RE(i, n) FOR(i, 1, n)
  18. #define FORD(i, a, b) for(int i = (a); i >= (b); --i)
  19. #define REP(i, n) for(int i = 0;i <(n); ++i)
  20. #define VAR(v, i) __typeof(i) v=(i)
  21. #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
  22. #define ALL(x) (x).begin(), (x).end()
  23. #define SZ(x) ((int)(x).size())
  24. #ifdef LOCAL
  25. #define debug(x) {cerr <<#x <<" = " <<x <<"\n"; }
  26. #define debug2(x, y) {cerr <<#x <<" = " <<x <<", "<<#y <<" = " <<y <<"\n";}
  27. #define debug3(x, y, z) {cerr <<#x <<" = " <<x <<", "<<#y <<" = " <<y <<", "<<#z<<" = "<<z<<"\n";}
  28. #define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }}
  29. using std::cerr;
  30. #else
  31. #define debug(x)
  32. #define debug2(x, y)
  33. #define debug3(x, y, z)
  34. #define debugv(x)
  35. #define cerr if(0)cout
  36. #endif
  37. #define make(type, x) type x; cin>>x;
  38. #define make2(type, x, y) type x, y; cin>>x>>y;
  39. #define make3(type, x, y, z) type x, y, z; cin>>x>>y>>z;
  40. #define make4(type, x, y, z, t) type x, y, z, t; cin>>x>>y>>z>>t;
  41. using std::endl;
  42. using std::cout;
  43. using std::cin;
  44. using std::vector;
  45. using std::set;
  46. using std::map;
  47. using std::pair;
  48. using std::max;
  49. using std::min;
  50. using std::ostream;
  51. using std::fixed;
  52. using std::ios_base;
  53. using std::setprecision;
  54. using std::make_pair;
  55. using std::string;
  56. using std::multiset;
  57. using std::next_permutation;
  58. using std::prev_permutation;
  59. using std::random_shuffle;
  60. using std::greater;
  61. using std::lower_bound;
  62. using std::upper_bound;
  63. using std::reverse;
  64. using std::swap;
  65. typedef long long ll;
  66. typedef long double LD;
  67. typedef pair<int, int> PII;
  68. typedef pair<ll, ll> PLL;
  69. typedef vector<int> VI;
  70. typedef vector<ll> VLL;
  71. typedef vector<pair<int, int> > VPII;
  72. typedef vector<pair<ll, ll> > VPLL;
  73.  
  74. template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
  75. template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
  76. template<class T1, class T2>
  77. ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
  78.  
  79. const int N = 44;
  80. const int INF = 1e7;
  81. int dis[N][N];
  82. int lay[N];
  83. int best_in_lay[N];
  84. int suf[N];
  85. int val[N];
  86. int best = 0;
  87. vector<int> layers[N];
  88. bool cmp(int a, int b) {
  89.   return val[a] > val[b];
  90. }
  91. int vis[N];
  92. int taken[N];
  93. vector<int> slo[N];
  94. bool Dfs(int v) {
  95.   vis[v] = 1;
  96.   if (v == 2) {
  97.     return true;
  98.   }
  99.   for (auto nei : slo[v]) {
  100.     if (vis[nei] || taken[nei]) {
  101.       continue;
  102.     }
  103.     if (Dfs(nei)) {
  104.       return true;
  105.     }
  106.   }
  107.   return false;
  108. }
  109.  
  110. void Rec(int layer, int last_v, int act_val) {
  111.   if (best >= act_val + suf[layer]) {
  112.     return;
  113.   }
  114.   if (layer == lay[2]) {
  115.     if (dis[2][last_v] != layer - lay[last_v]) {
  116.       return;
  117.     }
  118.     RE (i, N - 2) {
  119.       vis[i] = 0;
  120.     }
  121.     if (Dfs(1)) {
  122.       maxi(best, act_val);
  123.     }
  124.     return;
  125.   }
  126.   for (int v : layers[layer]) {
  127.     if (dis[v][last_v] != layer - lay[last_v]) {
  128.       continue;
  129.     } else {
  130.       taken[v] = 1;
  131.       Rec(layer + 1, v, act_val + val[v]);
  132.       taken[v] = 0;
  133.     }
  134.   }
  135.   Rec(layer + 1, last_v, act_val);
  136. }
  137.  
  138.  
  139.  
  140. #undef int
  141. int main() {
  142. #define int long long
  143.  
  144.   ios_base::sync_with_stdio(0);
  145.   cout << fixed << setprecision(10);
  146.   double beg = 1.0 * clock() / CLOCKS_PER_SEC;
  147.  
  148.   make(int, t);
  149.   RE (tt, t) {
  150.     make2(int, n, m);
  151.     FOR (i, 3, n) {
  152.       cin>>val[i];
  153.     }
  154.     RE (i, n) {
  155.       RE (j, n) {
  156.         dis[i][j] = N;
  157.       }
  158.       dis[i][i] = 0;
  159.       slo[i].clear();
  160.     }
  161.     RE (i, m) {
  162.       make2(int, a, b);
  163.       dis[a][b] = dis[b][a] = 1;
  164.       slo[a].PB(b);
  165.       slo[b].PB(a);
  166.     }
  167.     RE (k, n) {
  168.       RE (i, n) {
  169.         RE (j, n) {
  170.           mini(dis[i][j], dis[i][k] + dis[k][j]);
  171.         }
  172.       }
  173.     }
  174.  
  175.     REP (i, N) {
  176.       layers[i].clear();
  177.     }
  178.  
  179.     RE (i, n) {
  180.       lay[i] = dis[1][i];
  181.       layers[lay[i]].PB(i);
  182.     }
  183.  
  184.     FORD (i, n, 0) {
  185.       sort(layers[i].begin(), layers[i].end(), cmp);
  186.       if (SZ(layers[i])) {
  187.         suf[i] = suf[i + 1] + val[layers[i][0]];
  188.       }
  189.     }
  190.  
  191.     //was.clear();
  192.     best = 0;
  193.     //dfs1(0, 1, 0, vector<int>{1});
  194.     Rec(0, 1, 0);
  195.     cout<<best<<endl;
  196.   }
  197.  
  198.   return 0;
  199. }
  200.  
Runtime error #stdin #stdout 3.17s 3300KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/sHRqqQ
language:
C++14 (gcc 8.3)
created:
9 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!