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

};