fork(5) download
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <queue>
  5. #include <list>
  6. #include <climits>
  7. #include <string>
  8. #include <stack>
  9. #include <map>
  10. #include <set>
  11. #include <cmath>
  12. #include <cstdio>
  13. #include <cstring>
  14. #include <cstdlib>
  15. #include <sstream>
  16. #include <iomanip>
  17.  
  18. #define ALL(v) v.begin(), v.end()
  19. #define REP(i, a, b) for(int i = a; i < b; i++)
  20. #define REPD(i, a, b) for(int i = a; i > b; i--)
  21. #define REPLL(i, a, b) for(ll i = a; i < b; i++)
  22. #define FOR(i, a, b) for(int i = a; i <= b; i++)
  23. #define FORD(i, a, b) for(int i = a; i >= b; i--)
  24. #define FORLL(i, a, b) for(ll i = a; i <= b; i++)
  25. #define INF 1000000001
  26.  
  27. #define vit vector<int>::iterator
  28. #define sit set<int>::iterator
  29. #define vi vector<int>
  30. #define vpii vector<pii >
  31.  
  32. #define ll long long
  33. #define ld long double
  34.  
  35. #define pb push_back
  36. #define mp make_pair
  37. #define pii pair<int, int>
  38. #define pld pair<ld, ld>
  39. #define st first
  40. #define nd second
  41.  
  42. #define EPS 1e-9
  43. #define PI acos(-1.0)
  44. #define MAXN 40
  45.  
  46. using namespace std;
  47.  
  48. int z, n, m, a, b;
  49. int gold[MAXN];
  50. vi nbs[MAXN];
  51. vi nbsf[MAXN];
  52. int dist[MAXN];
  53. vi ls[MAXN];
  54. int layers;
  55. int cl[MAXN];
  56. int vis[MAXN];
  57. int mark[MAXN];
  58. int ret, x;
  59.  
  60. void bfs() {
  61. queue<int> q;
  62. q.push(0);
  63. REP(i, 0, n) dist[i] = INF;
  64. dist[0] = 0;
  65. while(q.size()) {
  66. int c = q.front(); q.pop();
  67. ls[dist[c]].pb(c);
  68. REP(i, 0, nbs[c].size()) {
  69. int nb = nbs[c][i];
  70. if(dist[nb] == INF) {
  71. dist[nb] = dist[c] + 1;
  72. q.push(nb);
  73. }
  74. }
  75. }
  76. layers = dist[1];
  77. cl[layers] = 1;
  78. cl[0] = 0;
  79. }
  80.  
  81. int dfs_back(int v) {
  82. if(v == 0) return 1;
  83. if(vis[v]++) return 0;
  84. if(mark[v]) return 0;
  85. REP(i, 0, nbs[v].size()) {
  86. if(dfs_back(nbs[v][i])) return 1;
  87. }
  88. return 0;
  89. }
  90.  
  91. void fl(int layer, int cur, int bag) {
  92. if(layer == layers) {
  93. if(cur == 1 && bag > ret) {
  94. memset(vis, 0, sizeof vis);
  95. if(dfs_back(1)) {
  96. //FOR(i, 0, layers) cout << cl[i] << " "; cout << endl;
  97. ret = max(ret, bag);
  98. }
  99. }
  100. return;
  101. }
  102. REP(i, 0, nbsf[cur].size()) {
  103. int nxt = nbsf[cur][i];
  104. mark[nxt] = 1;
  105. cl[layer+1] = nxt;
  106. bag += gold[nxt];
  107. fl(layer+1, nxt, bag);
  108. mark[nxt] = 0;
  109. cl[layer+1] = -1;
  110. bag -= gold[nxt];
  111. fl(layer+1, nxt, bag);
  112. }
  113. }
  114.  
  115. int main()
  116. {
  117. scanf("%d", &z); z++;
  118.  
  119. while(z-- > 1) {
  120. scanf("%d%d", &n, &m);
  121. ret = 0;
  122. FOR(i, 0, n) {
  123. nbs[i].clear();
  124. nbsf[i].clear();
  125. ls[i].clear();
  126. }
  127. memset(cl, -1, sizeof cl);
  128. memset(mark, 0, sizeof mark);
  129. memset(vis, 0, sizeof vis);
  130.  
  131. REP(i, 2, n) scanf("%d", &gold[i]);
  132. REP(i, 0, m) {
  133. scanf("%d%d", &a, &b);
  134. --a; --b;
  135. nbs[a].pb(b);
  136. nbs[b].pb(a);
  137. }
  138. bfs();
  139. REP(i, 0, n) {
  140. REP(j, 0, (int)nbs[i].size()) {
  141. int nb = nbs[i][j];
  142. }
  143. REP(j, 0, (int)nbs[i].size()) {
  144. int nb = nbs[i][j];
  145. if(dist[nb] > dist[i]) nbsf[i].pb(nb);
  146. }
  147. }
  148. fl(0, 0, 0);
  149. printf("%d\n", ret);
  150. }
  151.  
  152. return 0;
  153. }
  154.  
  155.  
  156.  
Success #stdin #stdout 0s 3344KB
stdin
Standard input is empty
stdout
Standard output is empty