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