TopCoder SRM 584, Division 1, Level 1 ( Division 2, Level 2 ) : Egalitarianism

概要

N 人の市民がいて、それぞれの友達関係が与えられる。
友達同士であるような二人の市民について、その所持金の差が d 以内になるようにしたとき、任意の二人の市民（友達同士でなくてもよい）の所持金の差の最大値はいくらになるか求めよ。
解が無限大になる場合は -1 で示せ。

解法

友達関係をグラフとして考えます。
このとき、全体が連結でない場合は異なるグループ間で所持金をいくらでも離すことができるので解はありません。

解が存在する状況下で解を得る方法について考えます。
辺の重みを 1 とすれば、距離 1 について d だけ所持金の差を広げることができます。
また、ある市民からある市民へのパスが二つ以上存在する場合、最短でないものを採用すると最短パスで辿ってきた場合の所持金の差が d を超えてしまうので、採用されるパスは最短経路のみであることがわかります。

最低の所持金額をもつ市民を一人仮定することを考えると、「所持金の差を d 広げる」は「所持金を d 増やす」と言い換えられます。
この場合の所持金の差の最大値は、仮定された所持金額が最低の市民から、その市民からの最短経路が最も長い市民への距離 × d です。
市民の数は高々 50 なのでこの試行を全市民について試すことができて、その場合は全ての頂点から他の全ての頂点への最短距離が必要になります。
従って、Warshall-Floyd 法で全点間最短距離を求めてから距離の最大値を求めると解けることが分かります。
Warshall-Floyd 法の結果として INF のまま更新されていない市民が残っている場合は到達できない == 連結でないので、最大値が INF になったら解はありません。

コード

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

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

const int INF = INT_MAX / 4;

class Egalitarianism
{
public:
	int maxDifference( vector <string> isFriend, int d )
	{
		const int N = isFriend.size();
		VVI G( N, VI( N, INF ) );
		REP( i, 0, N )
		{
			G[i][i] = 0;
		}
		REP( i, 0, N )
		{
			REP( j, 0, i )
			{
				G[i][j] = G[j][i] = isFriend[i][j] == 'Y' ? d : INF;
			}
		}

		REP( k, 0, N )
		{
			REP( i, 0, N )
			{
				REP( j, 0, N )
				{
					G[i][j] = min( G[i][j], G[i][k] + G[k][j] );
				}
			}
		}
		
		int res = 0;
		REP( i, 0, N )
		{
			res = max( res, *max_element( ALL( G[i] ) ) );
		}
		return res == INF ? -1 : res;
	}
};