TopCoder, SRM 638, Division 2, Level 3 : CandleTimerEasy

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13519&rd=16081

問題概要

　いくつかのロウソクが、木（ネットワークトポロジー的な意味で）状に配置されている。この木を使って時間を測ることを考える。計測の手順は、まず葉にあたるいくつかの端点に火を付け、全てのロウソクが燃え尽きるまでの時間によって時間を知る。
　火が節点に到達したとき、その節点に接続しているロウソクに火が移る。また、ロウソクは両側から燃えることもある。両側に同時に比が付いた場合、片側から燃やした場合の丁度半分の時間でロウソクガ燃え尽きる。
　各ロクソクについて、端点にある二つの節点の番号 及び、片側から燃やしたとき燃え尽きるのにかかる時間 が与えられる。測ることができる時間が何通りあるか、求めよ。
　

解法

　頂点数を と書きます。
　まず、 があまり大きくないので、オーダードリブンで、火の付け方を全通り試すことができることに気が付きます。火の付け方を決めたときに、全てのロウソクが燃え尽きるまでの時間を求めることができれば、std::set に入れるなどしてユニークなものの数を数えることができます。
　もし各節点の着火時刻 が分かっていれば、辺について走査して全体が燃え尽きるのにかかる時間を求められます。この場合、節点 間を結ぶ長さ のロウソク上（端点含む）の火が消える時刻は、 と、これ以降にロウソクが燃えている時間の和として求められます。両方の端点に火が付いてから、そのロウソクの残っている部分を片側から燃やしたときに掛かる時間は、 です。従って、このロクソクが燃え尽きる時刻は、 となります。このようにして求まる時刻を全ての辺について求め、それらの最大値を set::set に格納していけば、最後に size をとるだけで答えが求まります。
　以上の計算をするためには、各節点に火が付く時刻を知ることができなければなりません。節点に火が付く時刻とは、端点にいずれかの着火点から延焼してきた火が到達する時刻です。これは、その節点から最も近い着火点までの距離になります。従って、多点スタート Dijkstra 法などをすることで、全ての節点について火が到達する時刻を知ることができます。
　全ての火の付け方についてそれぞれ Dijkstara 法を実行しているので、このアルゴリズムは 時間で答えを出します。

コード

using VI = vector< int >; using VVI = vector< VI >;
using PII = pair< int, int >; using VPII = vector< PII >;
template < typename T = int > using VT = vector<T>; template < typename T = int > using VVT = VT< VT<T> >;
template < typename T = int > using LIM = numeric_limits< 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 EM emplace
#define EB emplace_back

#define fst first
#define snd second

constexpr int INF = LIM<>::max() / 2;

class CandleTimerEasy
{
public:
	int differentTime( vector <int> A, vector <int> B, vector <int> len )
	{
		const int V = A.size() + 1;
		transform( ALL( len ), len.begin(), bind( multiplies< int >(), _1, 2 ) );

		VT< VPII > G( V );
		REP( i, 0, A.size() )
		{
			const int a = A[i], b = B[i], l = len[i];
			G[a].EB( b, l );
			G[b].EB( a, l );
		}

		set< int > res;

		REP( s, 1, 1 << V )
		{
			priority_queue< PII, VPII, greater< PII > > que;
			VI distances( V, INF );

			bool ok = true;
			REP( i, 0, V )
			{
				if ( s & 1 << i )
				{
					que.EM( 0, i );
					distances[i] = 0;
					ok &= G[i].size() == 1;
				}
			}
			if ( !ok )
			{
				continue;
			}


			while ( !que.empty() )
			{
				const int dist = que.top().fst;
				const int u = que.top().snd;
				que.pop();

				if ( distances[u] < dist )
				{
					continue;
				}

				FOR( e, G[u] )
				{
					const int v = e.fst;
					const int d = e.snd;

					if ( dist + d < distances[v] )
					{
						que.EM( distances[v] = dist + d, v );
					}
				}
			}

			int tmp = 0;
			REP( i, 0, A.size() )
			{
				const int d1 = distances[ A[i] ], d2 = distances[ B[i] ];
				const int rest = len[i] - abs( d1 - d2 );
				tmp = max( tmp, max( d1, d2 ) + rest / 2 );
			}

			res.insert( tmp );
		}

		return res.size();
	}
};