fork(11) 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
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/8VYi2L
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

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!