Google Code Jam 2014, Round 1B, C : The Bored Traveling Salesman

問題文

http://code.google.com/codejam/contest/2994486/dashboard#s=p2

問題概要

　N 個の街があって、それぞれの街は固有の郵便番号をもっている。また、いくつかの街の間は空路で結ばれていてる。
　全ての街を訪れることができるように飛行機を予約したいが、以下の制約がある。

• 各チケットは往路と復路の二つのフライトからなる
• 復路のフライトを往路のフライトの前に使ってはならない
  • 往路と復路の間に他のチケットによるフライトを挟むことはできる
• 各街について、往路で入ってよいのは高々一回
• 予約したチケットのフライトは全て使わなければならない
• 各街を訪れる順番は任意
• 開始地点も任意

　この旅行中に、始めて訪れた街の郵便番号を訪れた順に連結して文字列を作る。valid な旅行であって、作られる文字列を辞書式順序で最小化したときのその文字列を求めよ。

解法

　辞書順最小といえば、手前がよければ後ろは適当でよいということを利用した Greedy アルゴリズムが定石となっています。この問題でもこれを利用できないか考えていきます。
　まず、露骨にグラフっぽいので、街を頂点、フライトを辺としたグラフを考えます。valid な旅行について考えると、（開始点に戻ってくるような明らかな無駄を除けば）往路のフライトによる辺だけを考えたグラフは有向木になっています。また、いくつかの往路のフライトをした後の復路のフライトの順序は確定していて、必ずより直近の往路のフライトに対応したものから使われます。これは FILO 構造で、スタックを用いることでシミュレートできます。
　さて本題です。訪問済み頂点の集合（空でもよい）が確定していて、次に（初回の）訪問をする頂点 v を仮定したとします。このときに valid な旅行を作れるか否かを求められれば、冒頭で書いた Greedy アルゴリズムを実装できます。
　未訪問頂点を 0, 往路で入ったがまだ復路で出ていない頂点を 1, それ以外（復路で離れた＝もう二度と来れない）頂点を 2 と分類します（valid な旅行が完了したときは全頂点は 2 になっています）。このとき、0, 1 の頂点のみからなる部分グラフが連結でなければ、全頂点を 2 にできないので、これは必要条件です。
　また、次に訪問すると仮定した頂点 v へ、他の未訪問頂点を経由せずに移動できなければなりません。これは、復路フライトを 0 回以上辿って、v と隣接している頂点に辿り着けるか否かと同値です。
　以上二つの、「0, 2 の頂点が連結」「v へ未訪問頂点を経由せずに遷移可能」を同時に満たすとき、次に v を訪問しても旅行全体を valid にできて、これは必要十分条件になっています。
　従って、この条件をチェックしつつ、郵便番号の文字列が小さい街から優先的に使う Greedy アルゴリズムによって問題を解くことができます。

コード

using VI = vector<int>;
using VVI = vector<VI>;
using VS = vector<string>;
template < typename T = int > using VT = vector<T>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) (c).begin(), (c).end()

#define PB( n ) push_back( n )

void dfs( const VVI &G, VI &used, VT<bool> &visited, const int v, const int p )
{
	visited[v] = true;
	FOR( u, G[v] )
	{
		if ( u == p || used[u] == 2 || visited[u] )
		{
			continue;
		}
		dfs( G, used, visited, u, v );
	}

	return;
}

bool validAddition( const int N, const int M, const VVI &G, const int root, VI used, stack<int> stk, const int v )
{
	while ( !stk.empty() && !binary_search( ALL( G[ stk.top() ] ), v ) )
	{
		used[ stk.top() ] = 2;
		stk.pop();
	}

	if ( stk.empty() )
	{
		return false;
	}

	VT<bool> visited( N );
	dfs( G, used, visited, root, -1 );
	REP( v, 0, N )
	{
		if ( used[v] != 2 && !visited[v] )
		{
			return false;
		}
	}
	return true;
}

string solve( const int N, const int M, const VS &ZIP, const VVI &G )
{
	VI cities( N );
	iota( ALL( cities ), 0 );
	sort( ALL( cities ), [&]( const int a, const int b ){ return ZIP[a] < ZIP[b]; } );
	const int root = cities[0];

	VI used( N );
	used[ root ] = 1;

	string res( ZIP[ root ] );

	stack<int> stk;
	stk.push( root );

	REP( iteration, 1, N )
	{
		FOR( v, cities )
		{
			if ( used[v] || !validAddition( N, M, G, root, used, stk, v ) )
			{
				continue;
			}

			while ( !binary_search( ALL( G[ stk.top() ] ), v ) )
			{
				used[ stk.top() ] = 2;
				stk.pop();
			}

			used[v] = 1;
			res += ZIP[v];
			stk.push( v );

			break;
		}
	}

	return res;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int t;
	cin >> t;

	REP( i, 0, t )
	{
		int n, m;
		cin >> n >> m;

		VS zip( n );
		FOR( z, zip )
		{
			cin >> z;
		}

		VVI G( n );
		REP( iteration, 0, m )
		{
			int a, b;
			cin >> a >> b;
			a--, b--;

			G[a].PB( b );
			G[b].PB( a );
		}
		FOR( V, G )
		{
			sort( ALL( V ) );
		}

		cout << "Case #" << i + 1 << ": " << solve( n, m, zip, G ) << endl;
	}

	return 0;
}