P1961 最轻的天平

Augen_stern · 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 初稿成！