网站顶部有空白成都百度业务员电话
问题描述
天平的两边有时不一定只能挂物品，还可以继续挂着另一个天平，现在给你一些天平的情况和他们之间的连接关系，要求使得所有天平都能平衡所需物品的总重量最轻。
一个天平平衡当且仅当“左端点的重量 × \times × 左端点到支点的距离 = = = 右端点的重量 × \times × 右端点到支点的距离。
输入格式
第一行包含一个 N ( N ≤ 100 ) N(N \le 100) N(N≤100)，表示天平的数量，天平编号为 1 1 1 到 N N N。
接下来包含 N N N 行描述天平的情况，每行 4 4 4 个整数 P , Q , R , B P,Q,R,B P,Q,R,B， P P P 和 Q Q Q 表示横杆上支点到左边的长度与到右边的距离的比例为 P : Q P:Q P:Q， R R R 表示左边悬挂的情况，如果 R = 0 R = 0 R=0 说明悬挂的物品，否则表示左边悬挂的是天平 R R R； B B B 表示右边的悬挂情况，如果 B = 0 B = 0 B=0 表示右边悬挂的是物品，否则右边悬挂着天平 B B B。
对于所有的输入，保证 W × L ≤ 2 31 W \times L \le 2^{31} W×L≤231，其中 W W W 为最轻的物品重量，而 L L L 为输入中描述左右比例时出现的最大值。
输出格式
输出一个整数表示使得所有天平都平衡所需最轻的物品总重量。
样例
样例输入1：
4
3 2 0 4
1 3 0 0
4 4 2 1
2 2 0 0
样例输出1：
40
数据范围
对于所有数据， N ≤ 100 , W × L < 2 31 N \le 100,W \times L < 2^{31} N≤100,W×L<231。
题解
考虑第 i i i 个天平，假设左右最轻重量为 W 1 , W 2 W1, W2 W1,W2，比例为 L 1 : L 2 L1:L2 L1:L2，当前需要左右放 X X X 和 Y Y Y。
则 X X X 和 Y Y Y 需要满足： W 1 × L 1 × X = W 2 × L 2 × Y W1 \times L1 \times X = W2 \times L2 \times Y W1×L1×X=W2×L2×Y。
移项可得： X Y = W 2 × L 2 W 1 × L 1 \frac{X}{Y} = \frac{W2 \times L2}{W1 \times L1} YX=W1×L1W2×L2。
因此，天平重量最小，必须将 x y \frac{x}{y} yx 化为最简分数。
求出 W 2 × L 2 W2 \times L2 W2×L2 和 W 1 × L 1 W1 \times L1 W1×L1 的最大公因数 P P P， X = W 2 × L 2 × P X = W2 \times L2 \times P X=W2×L2×P， Y = W 1 × L 1 × P Y = W1 \times L1 \times P Y=W1×L1×P。
重量为 X × W 1 + Y × W 2 X \times W1 + Y \times W2 X×W1+Y×W2。
处理时直接递归求解
#define int long long
int dfs(int x){if(x == 0){//边界return 1;}int t1 = dfs(l[x]), t2 = dfs(r[x]);int t = __gcd(a[x] * t1, b[x] * t2);return t1 * a[x] * t2 / t + t2 * b[x] * t1 / t;
}
signed main(){scanf("%d", &n);for(int i = 1; i <= n; ++ i){scanf("%d %d %d %d", &a[i], &b[i], &l[i], &r[i]);f[l[i]] = 1;f[r[i]] = 1;}int rt = 0;for(int i = 1; i <= n; ++ i){if(!f[i]){rt = i;break;}}printf("%lld", dfs(rt));return 0;
}