自动搬运

查看原文

来自洛谷，原作者为

	Augen_stern Du bist der ausschließliche Stern in meinen Augen. ||Du bist mein Augenstern. || 珍爱生命，远离 jcer

搬运于2025-08-24 21:32:20，当前版本为作者最后更新于2021-09-20 15:24:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Part 1：分析算法

由题可得：要想让一个天平平衡，首先要使得其左右天平平衡；

假设左右两边的最轻重量分别为 $W_1$，$W_2$，设该天平左右两边的比例为$L_1:L_2$；

而要想使得该天平衡，可能左边要放大倍数 $X$，右边要放大倍数 $Y$ 则有以下关系式： $W_1\times L_1\times X=W_2\times L_2\times Y$;

即 $\dfrac{X}{Y}=\dfrac{W_2\times L_2}{W_1\times L_1}$，要想使天平重量最小，但必须把 $\dfrac{X}{Y}$ 化为最简分数；

所以需要求出 $W_2\times L_2$ 和 $W_1\times L_1$ 的最大公约数 $P$；

则 $X=\dfrac{W_2\times L_2}{P}$，$Y=\dfrac{W_1\times L_1}{P}$，整个天平的重量为 $W_1\times X+W_2\times Y$。

Part 2：算法实现

经过分析我们可以来实现算法。

读入：

long long x;
long long a[105][105]; // 不开龙龙见祖宗；
int k[105];
scanf("%lld",&x);
for(long long i=1; i<=x; i++) {
	scanf("%lld%lld%lld%lld",&a[i][1],&a[i][2],&a[i][3],&a[i][4]);
	k[a[i][3]]=1;
	k[a[i][4]]=1;
}

然后在树上找根：

int root=0;
for(int i=1; i<=x; i++) {
	if(k[i]==0) root=i;
} // 有根树找根；

最后在这棵二叉树上遍历：

long long dfs(long long x) {
	if(x==0) return 1;
	long long left=dfs(a[x][3]); // 遍历左子树；
	long long right=dfs(a[x][4]); // 遍历右子树；
	long long P=__gcd(left*a[x][1],right*a[x][2]); // 求最大公因数 P；（直接用自带函数就行） 
	return left*right*a[x][2]/P+right*left*a[x][1]/P; // 得到总重量。
}

Part 3：CODE

完整代码走一波：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define INF 0x7fffffff;
using namespace std;
long long x;
long long a[105][105];
int k[105];
long long dfs(long long x) {
	if(x==0) return 1;
	long long left=dfs(a[x][3]);
	long long right=dfs(a[x][4]); // 左右树遍历；
	long long P=__gcd(left*a[x][1],right*a[x][2]); // 化简到最简分数；
	return left*right*a[x][2]/P+right*left*a[x][1]/P; // 得到总重量；
}
signed main() {
	scanf("%lld",&x);
	for(long long i=1; i<=x; i++) {
		scanf("%lld%lld%lld%lld",&a[i][1],&a[i][2],&a[i][3],&a[i][4]);
		k[a[i][3]]=1;
		k[a[i][4]]=1;
	} // 读入；
	int root=0;
	for(int i=1; i<=x; i++) {
		if(k[i]==0) root=i;
	} // 树上找根；
	printf("%lld",dfs(root)); // 搜索遍历并输出结果。
	return 0;
}

自给自足，丰衣足食！

2021.9.20 15:20 初稿成！