SRM 556 Div2 Medium XorTravelingSalesman

問題

ある都市iに渡ると現在の利益profitがprofit XOR cityValues[i]へと変わる. 自由に都市を何回でも渡れる時得られる利益の最大値を返せ.

解答

cityValuesの範囲は0-1023ととても小さいので,各都市iを訪れた時利益vが作れるかどうかという情報をM[i][v]=true or falseで管理する.M[i][v] = trueならば,都市iに隣接する都市に渡る.当然既に計算された都市と利益の組はそれ以上計算する必要はない.(枝刈りが出来る).

最大でも50*1024の状態を保存しておけばいいので,計算は高速.

class XorTravelingSalesman
{
public:
  int maxProfit(vector <int> cityValues, vector <string> roads)
    {
      int n = cityValues.size();
      int m = 1024;
      vector<vector<bool> > M(n, vector<bool>(m, false));
      // M[0][0] = true;
      vector<pair<int, int> >dfs;
      dfs.push_back(make_pair(0, cityValues[0]));
      int i;
      int res = 0;
      while(!dfs.empty()){
        pair<int, int> v = dfs.back();
        dfs.pop_back();
        int cur_idx = v.first;
        int cur_v = v.second;
        // printf("M[%d][%d]=%d\n", cur_idx, cur_v, (int)M[cur_idx][cur_v]);
        if (M[cur_idx][cur_v]) continue;
        M[cur_idx][cur_v] = true;
        res = max(res, cur_v);
        for(i = 0; i < n; i++){
          if (roads[cur_idx][i] == 'Y'){
            int next_v = cityValues[i]^cur_v;
            // cout << "next_v=" << next_v << endl;
            if (!M[i][next_v]){
              // M[i][next_v] = true;
              dfs.push_back(make_pair(i, next_v));
            }
          }
        }
      }
      return res;
    }
};