Not so Mobile(二叉树的DFS)

描述

传送门:UVa839

Before being an ubiquous communications gadget, a mobile was just a structure made of strings and wires suspending colourfull things. This kind of mobile is usually found hanging over cradles of small babies.

The figure illustrates a simple mobile. It is just a wire, suspended by a string, with an object on each side. It can also be seen as a kind of lever with the fulcrum on the point where the string ties the wire. From the lever principle we know that to balance a simple mobile the product of the weight of the objects by their distance to the fulcrum must be equal. That is $W_l × D_l = W_r × D_r$ where $D_l$ is the left distance, $D_r$ is the right distance, $W_l$ is the left weight and Wr is the right weight.

In a more complex mobile the object may be replaced by a sub-mobile, as shown in the next figure. In this case it is not so straightforward to check if the mobile is balanced so we need you to write a program that, given a description of a mobile as input, checks whether the mobile is in equilibrium or not.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The input is composed of several lines, each containing $4$ integers separated by a single space. The $4$ integers represent the distances of each object to the fulcrum and their weights, in the format: $W_l$ $D_l$ $W_r$ $D_r$
If $W_l$ or $W_r$ is zero then there is a sub-mobile hanging from that end and the following lines define the the sub-mobile. In this case we compute the weight of the sub-mobile as the sum of weights of all its objects, disregarding the weight of the wires and strings. If both $W_l$ and $W_r$ are zero then the following lines define two sub-mobiles: first the left then the right one.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
Write YES if the mobile is in equilibrium, write NO otherwise.

Sample Input

1
2
3
4
5
6
1
0 2 0 4
0 3 0 1
1 1 1 1
2 4 4 2
1 6 3 2

Sample Output

1
YES

思路

  • 紫书上的例题
  • 二叉树可以递归建立,同时本题的判断也可以递归进行。
  • 递归判断左右子天平是否平衡,然后将左右子天平看成一个物体来判断当前天平是否平衡。
  • 具体实现见代码orz

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
#define clr(a,x) memset(a, x, sizeof(a))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

// 返回子天平是否平衡,引用返回子天平的总重量
bool solve(int &w)
{
int w1, d1, w2, d2;
bool b1 = true, b2 = true;
cin >> w1 >> d1 >> w2 >> d2;
if (!w1) b1 = solve(w1);
if (!w2) b2 = solve(w2);
w = w1 + w2;
return b1 && b2 && (w1 * d1 == w2 * d2);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int t, w;
cin >> t;
while (t--)
{
if (solve(w))cout << "YES" << endl;
else
cout << "NO" << endl;
if (t)cout << endl;
}
return 0;
}
捐助作者