839 - Not so Mobile （UVA）

题目链接如下：

Online Judge

这道题刘汝佳的解法极其简洁，用了20来行就解决了问题。膜拜……

他的解法如下：天平（UVa839紫书p157）_天平 uva 839_falldeep的博客-CSDN博客

我写了两个（都很冗长），一开始一直报错，搞得我十分头大，后来发现是建立new node的时候left, right孩子没有初始化为nullptr……

第一个简洁一些，但是就算下面天平已经不平衡了，还是会一直计算到结束。代码如下：

#include <cstdio>
// #define debugstruct node{int wt, dis;node* left = nullptr;node* right = nullptr;
};
bool flag;void dfs(node* rt){rt->left = new node;rt->right = new node;scanf("%d %d %d %d", &rt->left->wt, &rt->left->dis, &rt->right->wt, &rt->right->dis);if (!rt->left->wt){dfs(rt->left);}if (!rt->right->wt){dfs(rt->right);}rt->wt = rt->left->wt + rt->right->wt;if (rt->left->wt * rt->left->dis != rt->right->wt * rt->right->dis){flag = false;}
}void deleteTree(node* rt){if (rt->left){deleteTree(rt->left);}if (rt->right){deleteTree(rt->right);}delete rt;
}int main(){#ifdef debugfreopen("0.txt", "r", stdin);freopen("1.txt", "w", stdout);#endifint n, kase;scanf("%d", &n);for (kase = 0; kase < n; ++kase){printf("%s", kase ? "\n" : "");flag = true;node* root = new node;dfs(root);printf("%s\n", flag ? "YES" : "NO");deleteTree(root);}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}

另一个是中间发现有问题了就可以提前跳出：

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
// #define debugstruct node{int wt, dis;node* left = nullptr;node* right = nullptr;
};
std::string line;
int n, kase, wl, dl, wr, dr, p;
std::vector<std::string> vec;
bool flag;void dfs(node* rt){std::stringstream in(vec[p++]);in >> wl >> dl >> wr >> dr;rt->left = new node;rt->left->wt = wl;rt->left->dis = dl;rt->right = new node;rt->right->wt = wr;rt->right->dis = dr;if (!rt->left->wt){dfs(rt->left);if (!flag){return;}rt->left->wt = rt->left->left->wt + rt->left->right->wt;}if (!rt->right->wt){dfs(rt->right);if (!flag){return;}rt->right->wt = rt->right->left->wt + rt->right->right->wt;}if (rt->left->wt * rt->left->dis != rt->right->wt * rt->right->dis){flag = false;}
}void deleteTree(node* rt){if (rt->left){deleteTree(rt->left);}if (rt->right){deleteTree(rt->right);}delete rt;
}int main(){#ifdef debugfreopen("0.txt", "r", stdin);freopen("1.txt", "w", stdout);#endifscanf("%d\n\n", &n);for (kase = 0; kase < n; ++kase){printf("%s", kase ? "\n" : "");while (getline(std::cin, line) && !line.empty()){vec.push_back(line);}flag = true;node *root = new node;p = 0;dfs(root);printf("%s\n", flag ? "YES" : "NO");vec.clear();deleteTree(root);}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}