uva 839 Not so Mobile

点击打开链接

题目意思：给定一序列的数字，每组四个，分别是W1 D1 W2 D2 表示左右节点的重量和长度，如果W1 或W2 为0说明有子节点存在，判断是否满足平衡

解题思路：1 建立二叉树，然后遍历查找 但是这个很麻烦  2 dfs 我们知道对于一颗树肯定是要先把左子树建完才能建右子树 我们可以用递归方式来代替建树直接求出左右两边的重量，判断是否相等  3 硬搞，这题数据很水，直接判断叶子节点是否全部满足平衡，如果是YES，其它都是NO（话说这样和标称ans不同，但是也可以AC哦）

代码1（dfs）：

//直接dfs，我们知道对于有0它肯定一直往下建树
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int t , w1 , w2 , d1 , d2 , flag;
//递归求解
void dfs(){
    scanf("%d%d%d%d" , &w1 , &d1 , &w2 , &d2);
    if(w1 == 0)
        w1 = dfs();
    if(w2 == 0)
        w2 = dfs();
    if(w1*d1 != w2*d2)
        flag = 0;
    return w1+w2;//返回重量
}
int main(){
    cin>>t;
    while(t--){
        flag = 1;//初始化为1
        dfs();
        if(flag)
            printf("YES\n");
        if(flag == 0)
            printf("NO\n");
        if(t)
            cout<<endl;
    }
}

/*这一题数据很水，所以我用直接判断叶子节点（对应的重量值全部为正数）对应是否全部满足平衡，如果有意个不满足就输出NO，否则YES.*/
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <stack>
#include <list>
#include <algorithm>
using namespace std;

const int MAXN = 1000010;
int  t , line , Index ,  node[MAXN][4] , flag;//node数组存储读入的数据

//处理问题的函数
void solve(){
    flag = 1;
    int i , j , lsum  = 0, rsum = 0;
    for(i = 0 ; i < Index ; i++){
       for(j = 0 ; j < 4 ; j++){   
           if(node[i][0] == 0 || node[i][2] == 0)//这一句重点，如果是重量为0不用考虑
               break;
       }
       if(j == 4){
           lsum = node[i][0] * node[i][1];
           rsum = node[i][2] * node[i][3];
           if(lsum != rsum){//如果有意个不满足直接输出NO  return回去
               printf("NO\n");
               return;
           }
      }
    }
    if(i == Index)//如果全部满足输出YES
        printf("YES\n");
}
//主函数
int main(){
    int i , j;
    cin>>t;
    for(j = 1 ; j <= t ; j++){
        line = 0 ; Index = 1;//Index表示有几行，只要重量为0，Index加一
        while(1){
            for(i = 0 ; i < 4 ; i++)
               scanf("%d" , &node[line][i]);
            if(node[line][0] == 0)
                   Index++;
            if(node[line][2] == 0)
                   Index++;
            ++line;
            if(line == Index) 
                break;
        }
        solve();
        if(j != t)
            cout<<endl;
    }
    return 0;
}