SRM556 Div1 Easy

250

探索

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;
  }
};