公式
A - 木の重み付け / Weighting a Tree 解説
by
A - 木の重み付け / Weighting a Tree 解説
by
physics0523
初心者の方へ
- AtCoder をはじめたばかりで何をしたらよいか分からない方は、まずは practice contest の問題A「Welcome to AtCoder」を解いてみてください。基本的な入出力の方法が載っています。
- また、プログラミングコンテストの問題に慣れていない方は、AtCoder Beginners Selection の問題をいくつか解いてみることをおすすめします。
- C++入門 AtCoder Programming Guide for beginners (APG4b) は、競技プログラミングのための C++ 入門用コンテンツです。
- Python入門 AtCoder Programming Guide for beginners (APG4bPython) は、競技プログラミングのための Python 入門用コンテンツです。
目的が \(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;
}
投稿日時:
最終更新:
