SRM 556 250pt : XorTravelingSalesman

問題概要

50頂点の無向グラフがある。0から始まる単純とは限らないパスをとり、各頂点に設定された値のxorをとった値の最大値を求める問題。値<1024。

考えたことなど

• XOR回廊を思い出すが値が小さい。そういうのを抜きにしても、間違ってもSRMのeasyでそんな深いところまで思考を飛ばしてはいけない。広く浅く考えるようにしないと。
• 頂点と値を組にしてflood fillするだけではないのか。
• まあたまにはこんな穏やかな回もあるか。
• 提出後、配列の宣言時に値と頂点数を逆にしていたことを忘れていて再提出痛い。

acceptされたコード

#include <vector>
#include <string>
using namespace std;

const int MAX_N = 50;
const int MAX_V = 1024;

int N;
int as[MAX_N];
bool graph[MAX_N][MAX_N];
bool visited[MAX_N][MAX_V];
int ANSWER = 0;

struct XorTravelingSalesman {

	int maxProfit(vector <int> cityValues, vector <string> roads) {
		N = cityValues.size();
		for (int i = 0; i < N; ++i) {
			as[i] = cityValues[i];
		}
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				graph[i][j] = roads[i][j] == 'Y';
			}
		}
		dfs(0, as[0]);
		return ANSWER;
	}

	void dfs(int v, int val) {
		updateMax(ANSWER, val);
		visited[v][val] = true;
		for (int i = 0; i < N; ++i) {
			if (graph[v][i] && !visited[i][val ^ as[i]]) {
				dfs(i, val ^ as[i]);
			}
		}
	}

};