1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <algorithm> 5 #include <iostream> 6 using namespace std; 7  8 #define MAXN 105 9 int score[MAXN];10 bool map[MAXN][MAXN];11 int path[MAXN];12 int dp[MAXN];13 14 void print_path(int x) {15     if (path[x] != 0)16         print_path(path[x]);17     printf("%d->", x);18 }19 20 int main() {21     int t, n, m;22     int i, j, k, tmp;23 24 #ifndef ONLINE_JUDGE25     freopen("data.in", "r", stdin);26 #endif27 28     scanf("%d", &t);29     for (k=1; k<=t; ++k) {30         scanf("%d", &n);31         for (i=1; i<=n; ++i)32             scanf("%d", &score[i]);33         score[n+1] = 0;34         memset(map, false, sizeof(map));35         memset(dp, 0, sizeof(dp));36         memset(path, 0, sizeof(path));37         scanf("%d", &m);38         while (m--) {39             scanf("%d %d", &i, &j);40             map[i][j] = true;41         }42         for (i=1; i<=n+1; ++i) {43             int max = 0, v = 0;44             for (j=1; j<i; ++j) {45                 if (map[j][i] && dp[j] >= max) {46                     max = dp[j];47                     v = j;48                 }49             }50             dp[i] = max + score[i];51             path[i] = v;52         }53         printf("CASE %d#\n", k);54         printf("points : %d\n", dp[n+1]);55         printf("circuit : ");56         print_path(path[n+1]);57         printf("1\n");58         if (k != t)59             printf("\n");60     }61 62     return 0;63 }