読者です 読者をやめる 読者になる 読者になる

SRM 584 Div2 Medium Egalitarianism

問題

SRM 584 - TopCoder Wiki

友達ネットワークが与えられた時に,友達同士の持ち金の差が高々d以下の時,任意の人同士の持ち金の差の最大を答える問題

解答

  • もし,友達ネットワークが全員に繋がっていなかったら-1を返す.
  • リンクを幅優先で辿った時に全員に到達するまでの最大ステップを求めれば良い.
  • 各ノードを開始ノードとした時の,到達ステップを計算し,最大のステップ数を求める.
using namespace std;

class Egalitarianism
{
public:
  int maxDifference(vector <string> isFriend, int d)
    {
      int n = isFriend.size();
      int i, j;
      int res = -1;
      for(i = 0; i < n; i++) {
        vector<bool> used(n, false);
        int max_count = 0;
        int max_link = 0;
        queue<pair<int, int> > q;
        q.push(make_pair(i, 1));
        while(!q.empty()) {
          int idx = q.front().first;
          int num_link = q.front().second;
          q.pop();
          if (used[idx]) continue;
          used[idx] = true;
          max_link = max(max_link, num_link);
          max_count++;
          for(j = 0; j < n; j++){
            if (isFriend[idx][j] == 'Y' &&
                used[j] == false) {
              q.push(make_pair(j, num_link + 1));
            }
          }
        }
        // cout << "i=" << i << " max_count=" << max_count
        //      << " max_link=" << max_link << endl;
        if (max_count == n) {
          res = max(res, max_link);
        }
      }
      if (res == -1) return -1;
      return (res-1) * d;
    }
};