SRM556 Div1 Easy

250

探索

view plainprint?

1. const int N = 50 + 1;  
2. const int V = 1024 * 2;  
3. bool vis[N][V];  
4.   
5. vector<string> G;  
6. vector<int> city;  
7.   
8. void rec(int node, int value)  
9. {  
10.   if (vis[node][value]) return ;  
11.   
12.   vis[node][value] = true;  
13.   for (int i = 0; i < G[node].size(); ++i) {  
14.     if (G[node][i] == 'Y') rec(i, value ^ city[i]);  
15.   }  
16.   return ;  
17. }  
18.   
19. class XorTravelingSalesman {  
20. public:  
21.   int maxProfit(vector <int> cityValues, vector <string> roads)  
22.   {  
23.     city = cityValues;  
24.     G = roads;  
25.     fill(&vis[0][0], &vis[N - 1][V - 1] + 1, false);  
26.   
27.     rec(0, cityValues[0]);  
28.   
29.     int mx = cityValues[0];;  
30.     for (int i = 0; i < N; ++i) {  
31.       for (int j = 0; j < V; ++j) {  
32.         if (vis[i][j]) mx = max(mx, j);  
33.       }  
34.     }  
35.   
36.     return mx;  
37.   }  
38. };  

const int N = 50 + 1;
const int V = 1024 * 2;
bool vis[N][V];

vector<string> G;
vector<int> city;

void rec(int node, int value)
{
  if (vis[node][value]) return ;

  vis[node][value] = true;
  for (int i = 0; i < G[node].size(); ++i) {
    if (G[node][i] == 'Y') rec(i, value ^ city[i]);
  }
  return ;
}

class XorTravelingSalesman {
public:
  int maxProfit(vector <int> cityValues, vector <string> roads)
  {
    city = cityValues;
    G = roads;
    fill(&vis[0][0], &vis[N - 1][V - 1] + 1, false);

    rec(0, cityValues[0]);

    int mx = cityValues[0];;
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < V; ++j) {
        if (vis[i][j]) mx = max(mx, j);
      }
    }

    return mx;
  }
};