SRM 584 div 1

初めての div1
1217 -> 1225
easyだけ解いてなんとかレートを維持した。
いろいろライブラリをつくっていく必要がありそう。

easy
グラフの連結成分が2つ以上ある場合は無限に差を大きくできる。
連結成分が1つだけのときは2頂点間の最短経路のうち最長の長さをみつければよい。
連結成分はDFSでチェックして、2頂点間の最短経路は各頂点からBFSをして求めた。
Warshall-Floyd法を使っている人が多かった。下手な実装をすると時間がかかりすぎるらしい。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;

typedef pair<int, int> P;
const int MAX_N = 50;
class Egalitarianism{
public:
	bool used[MAX_N];
	vector<string> isF;
	int N;
	void dfs(int p){
		for(int i = 0; i < N; i++){
			if(i == p) continue;
			if(isF[p][i] == 'Y' && !used[i]){
				used[i] = true;
				dfs(i);
			}
		}
	}
	int bfs(int s){
		int d[N], ret = -1;
		fill(d, d + N, -1);
		queue<P> Q;
		Q.push(P(s, 0));
		while(!Q.empty()){
			P p = Q.front(); Q.pop();
			int v = p.first;
			int c = p.second;
			if(d[v] != -1) continue;
			d[v] = c;
			ret = max(ret, c);
			for(int i = 0; i < N; i++){
				if(i == v) continue;
				if(isF[v][i] == 'Y' && d[i] == -1)
					Q.push(P(i, c + 1));
			}
		}
		return ret;
	}
	int maxDifference(vector <string> isFriend, int d){
		int ans = 0;
		isF = isFriend;
		N = isF.size();
		fill(used, used + MAX_N, false);
		used[0] = true;
		dfs(0);
		for(int i = 1; i < N; i++)
			if(!used[i]) return -1;
		for(int i = 0; i < N; i++)
			ans = max(ans, bfs(i));
		return ans * d;
	}
};