公式

A - 木の重み付け / Weighting a Tree 解説 by physics0523


初心者の方へ


目的が \(w_i \times r_i\) の 最小化 であることに注意します。
さらに、全ての \(w_i>0\) であるため、 \(r_i\) は小さくできるだけした方がよく、問題文を読むと全ての \(r_i\) を \(1\) にすることが許されており、かつそれが最小であることが分かります。

結局、入力で与えられた \(w_i\) の合計が答えとなります。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N;
  cin >> N;
  ll ans=0;
  for(ll i=1;i<N;i++){
    ll u,v,w;
    cin >> u >> v >> w;
    ans+=w;
  }
  cout << ans << "\n";
  return 0;
}

投稿日時:
最終更新: