Area1 https://blog.hatena.ne.jp/Area1/ Area1のif(memo[i][j]) https://area.hateblo.jp/ SRM グラフ DP 問題 N人の人間がいて、おのおの金を持っている。彼らの友好関係がvector string で与えられる。i番目の行のj番目が'Y'ならiとjは友人。'N'なら友人ではないとする。そして直接の友人間では持ち金の差は大きくともdとなるように調整されている。N人の持金の最大金額と最小金額の差の最大値を求めよ。いくらでも大きくできるときは-1を返せ。 やりかた 友人関係はグラフとして表現できる。グラフが連結でない時には連結していないノード間でいくらでも金額差を大きくできるので-1。つまりすごくリッチなグループをすごく貧乏なグループの差をいくらでも大きくできてしまう。 連結であれば点対間の最短距離が最… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Farea.hateblo.jp%2Fentry%2F2013%2F07%2F10%2F223113" title="SRM 584 Div1 Easy / Div2 Medium Egalitarianism - Area1のif(memo[i][j])" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2013-07-10 22:31:13 rich https://area.hateblo.jp/entry/2013/07/10/223113 1.0 100%