TCO12 300pt : GreedyTravelingSalesman
問題概要
重み付き有向完全グラフが与えられる。ノード0からスタートしてもっともコストが小さい辺を選んで未訪問のノードへ行く。1本辺を選んでコストを書き換え、全てのノードを訪ねるのに必要なコストを最大化する問題。
解法
どの辺をどの長さに書き換えるかを色々試してシミュレーションする。書き換える長さを1~9999全部試すとTLEだが、座標圧縮っぽく他の辺と同じか-1か9999だけ試せばよい。0にはできないことに注意。
acceptされたコード
こんな場合分け多いコードが通ったのは運がよかっただけ。
#include <cstdio> #include <vector> #include <string> #include <cstring> #include <algorithm> using namespace std; const int MAX_N = 30; int graph[MAX_N][MAX_N]; bool visited[MAX_N]; struct GreedyTravelingSalesman { int worstDistance(vector <string> thousands, vector <string> hundreds, vector <string> tens, vector <string> ones) { const int N = thousands.size(); for(int i=0; i<N; ++i){ for(int j=0; j<N; ++j){ graph[i][j] = (thousands[i][j]&15)*1000 + (hundreds[i][j]&15)*100 + (tens[i][j]&15)*10 + (ones[i][j]&15); } } int ans = 0; //cost(i,j) -> 9999 for(int i=0; i<N; ++i){ for(int j=0; j<N; ++j){ int tmp = graph[i][j]; graph[i][j] = 9999; int cur = 0, total = 0; memset(visited, false, sizeof(visited)); for(;;){ visited[cur] = true; int mini = 10000, key = -1; for(int k=0; k<N; ++k){ if(!visited[k] && mini > graph[cur][k]){ mini = graph[cur][k]; key = k; } } if(key == -1){ break; } total += mini; cur = key; } graph[i][j] = tmp; ans = max(ans, total); } } //cost(i,j) == lowest to choose for(int i=0; i<N; ++i){ for(int j=0; j<N; ++j){ int cur = 0, total = 0; memset(visited, false, sizeof(visited)); for(;;){ visited[cur] = true; int mini = 10000, key = -1; for(int k=0; k<N; ++k){ if(!visited[k] && mini > graph[cur][k]){ mini = graph[cur][k]; key = k; } } if(key == -1){ break; } total += mini; if(i == cur && !visited[j]){ if(key != j){ if(key > j){ cur = j; } else if(mini > 1){ cur = j; --total; } else{ cur = key; } } else { total -= mini; mini = 10000; int m1 = 9999, m2 = 9999; for(int k=0; k<N; ++k){ if(!visited[k] && k < j){ m1 = max(1, min(m1, graph[cur][k] - 1)); } else if(!visited[k] && k > j){ m2 = max(1, min(m2, graph[cur][k])); } } total += min(m1, m2); cur = key; } } else{ cur = key; } } ans = max(ans, total); } } return ans; } };