UVA.839 Not so Mobile ( 二叉树 DFS)

题意分析

给出一份天平，判断天平是否平衡。

一开始使用的是保存每个节点，节点存储着两边的质量和距离，但是一直是Runtime error。也不知道到底是哪里出了问题，后来发现直接判断当前是否平衡，若下面还有节点，接着递归调用dfs判断，这样一来省去了存储节点所需要的空间和时间，效率大大提升。

代码总览

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

#include <sstream>

#include <queue>

#include <stack>

#include <set>

#include <map>

#include <vector>

#define nmax 10000000

#define INF 0x3f3f3f3f

using namespace std;

struct node{

    int lwei,rwei;

    int ldis,rdis;

    bool risend,lisend;

};

bool isbalence;

bool cal (struct node p)

{

    if(p.ldis * p.lwei == p.rdis * p.rwei) return true;

    else return false;

}

int dfs()

{

    struct node p;

    scanf("%d%d%d%d",&p.lwei,&p.ldis,&p.rwei,&p.rdis);

    if(p.lwei == 0) p.lwei = dfs();

    if(p.rwei == 0) p.rwei = dfs();

    if(!cal(p)) isbalence = false;

    return (p.lwei+p.rwei);

}

int main()

{

    int t;

    scanf("%d",&t);

    bool first = true;

    while(t--){

        isbalence = true;

        dfs();

        if(t) printf("%s\n\n",isbalence?"YES":"NO");

        else printf("%s\n",isbalence?"YES":"NO");

    }

    return 0;

}