SRM556Div2
Medium:
グラフと、各頂点の値が渡されるので、スタート地点からグラフを移動し、値をXORしていった時に得られる最大値を求める問題。
同じノードを複数回訪れる事も可能。
無向グラフなら
a->b->c->b->a という風に来た道を戻れば任意の値を使えるので、到達できる頂点の値をXORしたときの最大値だと思って解いた。
#include <cstdlib> #include <cmath> #include <map> #include <utility> #include <set> #include <iostream> #include <string> #include <vector> #include <algorithm> #include <sstream> #include <complex> #include <stack> #include <queue> #define REP(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) REP(i,0,n) using namespace std; class XorTravelingSalesman { public: int maxProfit(vector <int> cityValues, vector <string> roads) { int result=0; set<int> enableValues; queue<int> q; q.push(0); enableValues.insert(cityValues[0]); while(!q.empty()) { int n=q.front();q.pop(); rep(i,roads.size()) { if( roads[n][i]=='Y' ) { enableValues.insert(cityValues[i]); q.push( i ); roads[n][i]='N'; } } } q.push(0); set<int> visited; visited.insert(0); while( !q.empty() ) { int n = q.front();q.pop(); for( set<int>::iterator it = enableValues.begin(); it!=enableValues.end(); ++it ) { if( visited.find(n^(*it)) == visited.end() ) { visited.insert(n^(*it)); q.push( n^(*it)); result = max( result , n^(*it)); } } } return result; }