AOJ : 0520 - 最軽量のモビール (Lightest Mobile)
問題概要
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0520&lang=jp
日本語の問題文なので, 説明はなしです
アルゴリズム
この問題の入力は, かならず2分木になることがわかります.
この木のルートから探索を始めて, 深さ優先で木を探索していきます.
再帰関数の戻り値として, 「現在見ている棒より下のモビールの最小重量」を返すようにしておきます. そうすれば, 木の深いところから順番に, 最小の重量が決まっていき, 最終的に全体の最小重量が決定できます.
モビールの最小重量は,
(その棒の赤の端より下につるされている錘の重さの総計) × (その棒の支点から赤の端までの長さ) = (その棒の青の端より下につるされている錘の重さの総計) × (その棒の支点から青の端までの長さ)''
となるように, 「最小公倍数」で決定できます.
プログラム
#include <iostream> #include <cstring> using namespace std; int n,p[101],q[101],r[101],b[101]; bool flg[101]; //上からつるされているかのフラグ //最大公約数 int gcd(int a,int b){ return b == 0 ? a : gcd(b,a%b); } //最小公倍数 int lcm(int a,int b){ return a / gcd(a,b) * b; } int solve(int idx){ int res = 0; int rcost = r[idx] ? solve(r[idx]) : 1; int bcost = b[idx] ? solve(b[idx]) : 1; int l = lcm(p[idx] * rcost, q[idx] * bcost); return l / p[idx] + l / q[idx]; } int main(void){ while(cin>>n, n){ memset(flg,0,sizeof(flg)); for(int i=1;i<=n;i++){ cin>>p[i]>>q[i]>>r[i]>>b[i]; flg[r[i]] = flg[b[i]] = true; //上からつるされている棒をtrueにする } for(int i=1;i<=n;i++){ //上からつるされていない棒ならば, ルートノード if(!flg[i]){ cout<<solve(i)<<endl; break; } } } return 0; }