PAT甲级的题目有关于树的题目，1053，1086，1090，1102，1106，1115，1119，1038，1110，1020，1043
A1053
这题目比较简单，给定一棵树，给定一个数字，要你找到所有和等于给定数字的路径。这个题目的树没有给出是二叉树，自然不能按照原来二叉树的方法来构建了。其实就是BFS，用DFS也是可以的，不过考虑到DFS还要新开一个数组来存储路径，还是使用BFS。
首先是树的结构，只需要在原来二叉树的基础上修改一下就好了。
typedef struct treeNode {
int val;
int weight;
vector<struct treeNode *> generator;
int parent = -1;
} *TreeNode, treeNode;
把原来的左右子树修改成一个vector存储即可。树的结构中新添加了一个parent，是用于找到根节点，因为题目给出的树是一个列表，接着是树的父节点，不添加parent找不到父节点。如果parent是-1那么就是根节点了。
TreeNode createTree(int n, TreeNode *array, int allNodes) {
for (int i = 0; i < n; ++i) {
int index;
int num;
cin >> index >> num;
index_map[index] = true;
for (int j = 0; j < num; ++j) {
int next;
cin >> next;
array[next]->parent = index;
array[index]->generator.push_back(array[next]);
}
sort(array[index]->generator.rbegin(), array[index]->generator.rend(), cmp);
}
for (int k = 0; k < allNodes; ++k) {
if (array[k]->parent == -1) {
return array[k];
}
}
return nullptr;
}
创建树的过程，注意后面有一个排序操作，题目的输出要求按照次序输出。然后就是BFS操作了。
void findWeights(TreeNode root, int sum, vector<int> weightsAdd, int equalWeights) {
if (sum > equalWeights) {
return;
} else if (sum < equalWeights) {
sum += root->weight;
weightsAdd.push_back(root->weight);
if (sum == equalWeights) {
if (!index_map[root->val]) {
weights_path.push_back(weightsAdd);
weightsAdd.clear();
}
return;
}
for (int i = 0; i < root->generator.size(); ++i) {
TreeNode current = root->generator[i];
findWeights(current, sum, weightsAdd, equalWeights);
}
}
}
BFS把weightsAdd当成是一个拷贝过来的局部变量，不需要回滚操作，比DFS简单多了。然后就是输出了，只需要注意最后不要空格就好。
其实也可以用数组来完成，所占空间可能更小。
1086
这个题目做了很久，要是在上机考试碰见这个题目应该就只有10来分了。题目大意是给定一个入栈出栈的序列，这个出入栈完成后得到的出栈序列是中序遍历的序列，要你求这棵树的后续遍历。我直接从序列入手，发现push操作就是：如果当前节点有左子树，就插入左子树，否则就插入右子树；pop操作是回退到上一课树，按照这个操作就可以创建出一棵树，然后后续遍历即可。然而内存爆炸了。
之前考408的时候遇到过这样的操作，好像是天勤ds里面，中序遍历如果使用栈来实现，入栈顺序就是前序遍历次序。所以题目表面上是给了一个序列，实际上给了前序和中序遍历，让你求后续遍历。这个就很简单了。
TreeNode create(int preL, int preR, int inL, int inR, int *preOrder, int *inOrder) {
int rootNum = preOrder[preL];
TreeNode root = new treeNode;
root->val = rootNum;
if (preL == preR) {
root->val = rootNum;
root->leftChild = root->rightChild = nullptr;
return root;
}
if (preL > preR) {
return nullptr;
}
int mid = -1;
for (int i = inL; i <= inR; ++i) {
if (inOrder[i] == rootNum) {
mid = i;
break;
}
}
int leftNumber = mid - inL;
int rightNumber = inR - mid;
root->leftChild = create(preL + 1, preL + leftNumber, inL, mid - 1, preOrder, inOrder);
root->rightChild = create(preR - rightNumber + 1, preR, mid + 1, inR, preOrder, inOrder);
return root;
}
关键就是创建树的操作，天勤的代码题出过这类，主要就是前中序遍历的边界数对就行。
1090
这个题目一开始读的没太懂，两次都超了，只有14分。一开始还以为最后要给出的是路径上零售商的数量，没想到是路径的个数。
很明显是BFS，和上上题一样：
//typedef struct treeNode {
// int val;
// vector<struct treeNode *> children;
// int parent = -1;
//} *TreeNode, treeNode;
double maxPrice = -1;
int maxNumber = -1;
//void BFS(TreeNode root, double currentPrice, double r, vector<int> path) {
// if (root) {
// path.push_back(root->val);
// currentPrice = currentPrice * ((100 + r) / 100);
// if (maxPrice < currentPrice) {
// maxPrice = currentPrice;
// maxNumber = path.size();
// }
// for (int i = 0; i < root->children.size(); ++i) {
// BFS(root->children[i], currentPrice, r, path);
// }
// }
//}
建树是不行的，直接就内存爆炸。如此那就直接用数组吧，于是想到从尾巴开始，然而题目有关键一句：It is assumed that each member in the supply chain has exactly one supplier except the root supplier, and there is no supply cycle.假设在供应链上的每名成员都只有一个供应者，除了根部的供应者，没有环，那么就不需要像图一样设置访问标记。
// for (int j = 0; j < n; ++j) {
// if (!visited[j]) {
// int paths = 0;
// int fa = array[j];
// while (fa != -1) {
// visited[fa] = true;
// fa = array[fa];
// paths++;
// }
// maxNumber = ((maxNumber > paths) ? maxNumber : paths);
// }
// }
还是超时了，因为如果从底部开始，会出现很多重复的道路，所以最好还是从底部开始访问，我也是在这里看了别人题解之后才知道，原来输出的最后一个数字应该是路径的个数，翻译错了。
vector<int> v[100010];
void bfs(int root, int depth) {
if (v[root].size() == 0) {
if (maxPrice < depth) {
maxPrice = depth;
maxNumber = 1;
} else if (maxPrice == depth) {
maxNumber++;
}
return;
}
for (int i = 0; i < v[root].size(); ++i) {
bfs(v[root][i], depth + 1);
}
}
用一个vector数组把所有儿子串起来，遍历访问即可。
1102
输入详情：每一个输入包含了一个测试样例。对于每一个例子，第一行给出一个正整数，也及是树的总节点数，因此，节点编号从0到N-1，然后下面N行每一行对应节点0到N-1，每一行给出左右子树。如果子树不存在，用-来代替，每一对孩子用空格分离。
输出详情：对于每一个样例，第一行打印翻转树的层序遍历序列，然后第二行打印翻转树的中序遍历序列，用空格隔开，最后不能有空格。
这个题目就非常简单了，唯一的考点就是交换两树的左右子树，直接后序遍历交换就好了，释放树的内存也是后序遍历实现。
for (int i = 0; i < n; ++i) {
array[i].val = i;
string left, right;
cin >> left >> right;
if (left == "-") {
array[i].leftChild = nullptr;
} else {
array[i].leftChild = &array[string2Number(left)];
array[string2Number(left)].parent = i;
}
if (right == "-") {
array[i].rightChild = nullptr;
} else {
array[i].rightChild = &array[string2Number(right)];
array[string2Number(right)].parent = i;
}
}
创建树和前面几个题目一样。
void postExchange(TreeNode root) {
if (root) {
postExchange(root->leftChild);
postExchange(root->rightChild);
TreeNode temp = root->leftChild;
root->leftChild = root->rightChild;
root->rightChild = temp;
}
}
1106
一条供应链网络由零售商，经销商，供应商组成，每一总角色在这条网络（产品从生产者到消费者）中都起到相应的作用。从根节点的供应者开始，每个人从供应商以P的价格购买，以比P价格高上百分之r的价格卖给经销商或者是零售商。只有零售商才会面对客户，假设每一个成员只有一个提供者，而且没有循环。
输出详情：每一个输入包含一个测试样例。对于每一个样例，第一行包含一个正整数，标识供应链中成员总数，P标识根供应者的价格，也就是初始价格。r是比率，每经过一个经销商或者是零售商价格需要提升r比率。接下来N行中，每一行描述的格式：K,ID,......。第i行中Ki表示总共有Ki个接受者，其实就是说第i号的提供者有这么多个接受者。中间空格隔开。
输出详情：对于每一个测试样例，打印出零售商的最低价格，也就是最后一个`叶子的最低价格，精确到四位小数，有多少个零售商可以拿到最低价格。
读完题，一看就知道BFS，和前面那道题没有什么区别。
void BFS(int root, int depth, treeNode *array) {
if (depth > minDepth && minNumber > 0) {
return;
}
if (array[root].childen.size() == 0) {
if (depth < minDepth) {
minDepth = depth;
minNumber = 1;
} else if (depth == minDepth) {
minNumber++;
}
return;
}
for (int i = 0; i < array[root].childen.size(); ++i) {
BFS(array[root].childen[i], depth + 1, array);
}
}
仅仅修改此处即可。不过值得注意的是，我一开始是创建了一颗树，后来发现超时，我一开始还以为是递归调用超时，于是我添加了：
if (depth > minDepth && minNumber > 0) {
return;
}
如果已经找到了一个更短的，那么如果还有，要么和其相同，要么更短，所以如果还有比他长的直接去掉。但是加上后PAT评测的时间有减少，但是还是有两个数据是段错误，修改一下，把一些多余数据去掉就可以了。推测原因应该是内存超限了。
1115
这个题目就不翻译了，非常简单，就要你找倒数第一和倒数第二层的节点数加起来。层序遍历是最为适合的了，BFS也可以。关键有几个地方，构建树：
TreeNode insert(TreeNode root, int num) {
if (root) {
if (root->val < num) {
root->rightChild = insert(root->rightChild, num);
} else {
root->leftChild = insert(root->leftChild, num);
}
return root;
} else {
root = new treeNode;
root->val = num;
root->leftChild = root->rightChild = nullptr;
return root;
}
}
在树的结构中添加一个层次属性，记录属于第几层。
void level(TreeNode root) {
fill(depth, depth + MAX, 0);
queue<TreeNode> Queue;
Queue.push(root);
while (!Queue.empty()) {
TreeNode cur = Queue.front();
Queue.pop();
depth[cur->depth]++;
maxDepth = ((maxDepth > cur->depth) ? maxDepth : cur->depth);
if (cur->leftChild) {
cur->leftChild->depth = cur->depth + 1;
Queue.push(cur->leftChild);
}
if (cur->rightChild) {
cur->rightChild->depth = cur->depth + 1;
Queue.push(cur->rightChild);
}
}
}
每一次取出节点的时候顺便直接存进数组里面计数，免得害得遍历一次数组。水题一道。
1119
假设在二叉树中所有的关键字都是互不相同的正整数。一颗独一无二的二叉树可以由一对后序和中序遍历序列得到，或者是前序和中序得到。但是，如果只给了后续和前序遍历，那么对应的二叉树并非是唯一的。
现在给一串后序和中序遍历序列，你应该要输出对应的中序遍历的序列，如果此树不唯一，只需要输出他们其中一个即可。
输入详情：每一个输入包含一个测试样例，对于每一个样例，第一个是一个正整数，表示整个二叉树有多少个节点。第二行给出前序遍历序列，第三行给出后续遍历序列，所有的数字之间右空格分隔。
输出详情：对于每一个测试样例，如果树是唯一的，输出yes，如果不是，输出no。下一行输出中序遍历序列。如果解不是唯一的，任何答案都可以。保证至少有一个解。
这个题目第一眼看到是一点思路都没有，上了考场标准0分。首先分析一下前序遍历和后续遍历。前序遍历：根，左子树，右子树；后序遍历：左子树，右子树，根。那么如果这一棵树都有左右子树，那么这棵树就是唯一的，如果这棵树只有左子树，或者右子树，那就有可能有多种情况，这唯一的一棵树可以在左边也可以在右边。这也就是为什么不能唯一确定的原因，这个问题在考408的时候都没有深究。
那么关键就是切分了：
TreeNode create(int preL, int preR, int postL, int postR, int *preSequences, int *postSequences) {
if (preL > preR) {
return nullptr;
}
TreeNode root = new treeNode;
root->val = preSequences[preL];
root->leftChild = root->rightChild = nullptr;
if (preL == preR) {
return root;
}
如果如果只有一个元素，说明就是一个节点，没有左右子树，直接返回。
if (k - preL > 1) {
root->leftChild = create(preL + 1, k - 1, postL, postL + k - preL - 2, preSequences, postSequences);
root->rightChild = create(k, preR, postL + k - preL - 1, postR - 1, preSequences, postSequences);
} else {
flag = false;
root->leftChild = create(k, preR, postL + k - preL - 1, postR - 1, preSequences, postSequences);
}
如果发现包括根节点在内是大于1的，那么说明存在左右子树，那么肯定唯一，如果不是大于1，那说明只有一颗子树，放左放右都可以。最后遍历即可。
1083
给出一段数字,你应该可以用他们组成最小的数字，举个例子，我们组成许多数字如32-321-0229-87or0229-321-3214等等不同组成方式的数字段。
这个题目真的非常简单，之前在洛谷刷过差不多的。主要是几个字符串比较的情况，如123 1230，如果是这样，排序必须是1230123，因为最后的0是小于前面的第一个数1的，但如果是123 1235，那么就要倒过来了，1231235。其实就是贪心就好了。我也不知道为什么这个题目会归类到树这一块。
int cmp(string a, string b) {
return a + b < b + a;
}
这句就是最关键的了，注意一些特殊情况，当全是0的时候要输出0即可。之前就是因为直接把打头的0去掉，导致如果result = 0那么什么都不输出。
1147
水题一道，题目直接给出是完全二叉树了，直接用数组表示即可。
bool isHeap(int *array, int n, bool maxHeap) {
for (int i = 1; i <= n / 2; ++i) {
int left = i * 2;
int right = left + 1;
if (left <= n) {
if (maxHeap) {
if (array[left] > array[i]) {
return false;
}
} else {
if (array[left] < array[i]) {
return false;
}
}
}
if (right <= n) {
if (maxHeap) {
if (array[right] > array[i]) {
return false;
}
} else {
if (array[right] < array[i]) {
return false;
}
}
}
}
return true;
}
考查一下是否符合堆的要求即可。
1151
这个题目写出来本以为胜券在握，这个规律很好找，前序遍历是根左右，中序遍历是左根右，那么在中序遍历里面给出的两个关键字的根一定在两个关键字之间，比如中序遍历7 2 3 4 6 5 1 8，找26的最短祖先，祖先看定在3，4之间。对于前序遍历，祖先肯定在26的前面，以此类推就好了。
所以首要一步就是要找到当前两个关键字的位置，然后看他中间的数是不是在前序遍历的那两个关键字的前面即可。一开始是直接遍历找位置，结果超时了。
// map<int, bool> map_match;
//
// int first, second;
//
// if (aIndex > bIndex) {
// first = bIndex;
// second = aIndex;
// } else {
// first = aIndex;
// second = bIndex;
// }
//
// for (int j = first; j <= second; ++j) {
// map_match[inOrder[j]] = true;
// }
//
// for (int l = 0; l <= aPreIndex && l <= bPreIndex; ++l) {
// if (map_match[preOrder[l]]) {
// if (preOrder[l] != a && preOrder[l] != b) {
// cout << "LCA of " << a << " and " << b << " is " << preOrder[l] << "." << endl;
// break;
// } else if (preOrder[l] == a) {
// cout << a << " is an ancestor of " << b << "." << endl;
// break;
//
// } else if (preOrder[l] == b) {
// cout << b << " is an ancestor of " << a << "." << endl;
// break;
//
// }
// }
// }
超时的想法是先把中序遍历里面的在关键字之间的变量都存在一个map里面，然后遍历前序遍历直到遇到关键字，结果超时了。在输入的时候，就应该事先把遍历的位置用map存下来，然后就只需要遍历一次了：
//
// Created by GreenArrow on 2020/3/15.
//
#include <iostream>
#include <map>
using namespace std;
int main() {
int m, n;
cin >> m >> n;
int preOrder[n];
int inOrder[n];
map<int, int> positionPre, positionIn;
for (int i = 0; i < n; ++i) {
cin >> inOrder[i];
positionIn[inOrder[i]] = i;
}
for (int j = 0; j < n; ++j) {
cin >> preOrder[j];
positionPre[preOrder[j]] = j;
}
for (int k = 0; k < m; ++k) {
int a, b;
cin >> a >> b;
int aIndex = -1;
int bIndex = -1;
int aPreIndex = -1;
int bPreIndex = -1;
if (positionIn.count(a)) {
aIndex = positionIn[a];
}
if (positionIn.count(b)) {
bIndex = positionIn[b];
}
if (aIndex == -1 && bIndex == -1) {
cout << "ERROR: " << a << " and " << b << " are not found." << endl;
continue;
} else if (aIndex != -1 && bIndex == -1) {
cout << "ERROR: " << b << " is not found." << endl;
continue;
} else if (aIndex == -1) {
cout << "ERROR: " << a << " is not found." << endl;
continue;
}
if (a == b) {
cout << a << " is an ancestor of " << b << "." << endl;
continue;
}
for (int i = 0; i < n; ++i) {
int temp = preOrder[i];
int inPosition = positionIn[temp];
if (temp == a) {
cout << a << " is an ancestor of " << b << "." << endl;
break;
} else if(temp == b){
cout << b << " is an ancestor of " << a << "." << endl;
break;
}
if(inPosition > aIndex && inPosition < bIndex){
cout << "LCA of " << a << " and " << b << " is " << temp << "." << endl;
break;
} else if(inPosition > bIndex && inPosition < aIndex){
cout << "LCA of " << a << " and " << b << " is " << temp << "." << endl;
break;
}
}
1110
这个题目想了挺久的，有点意思，完全二叉树的数组是全满的，所以只需要看看数组是不是全部能访问就好了。首先建树找根节点：
for (int i = 0; i < n; ++i) {
string left, right;
cin >> left >> right;
if (left == "-") {
array[i].left = -1;
} else {
array[i].left = string2number(left);
father[array[i].left] = i;
}
if (right == "-") {
array[i].right = -1;
} else {
array[i].right = string2number(right);
father[array[i].right] = i;
}
}
int root = -1;
for (int j = 0; j < n; ++j) {
if (father[j] == -1) {
root = j;
}
}
father的用处就是看看是不是根节点而已。没有什么太大用处，接着就是遍历填数组了，用前中后序遍历填写都可以，这里还是用层次遍历好了：
int level(node *array, int root, int *array_tree) {
queue<int> Queue;
Queue.push(root);
array[root].index = 0;
array_tree[array[root].index] = 1;
vector<int> sequences;
while (!Queue.empty()) {
int cur = Queue.front();
sequences.push_back(cur);
Queue.pop();
if (array[cur].left != -1) {
Queue.push(array[cur].left);
array_tree[array[cur].index * 2 + 1] = 1;
array[array[cur].left].index = array[cur].index * 2 + 1;
}
if (array[cur].right != -1) {
Queue.push(array[cur].right);
array_tree[array[cur].index * 2 + 2] = 1;
array[array[cur].right].index = array[cur].index * 2 + 2;
}
}
return sequences[sequences.size() - 1];
}
然后只要看看遍历过的数组有没有空的，有空的那就不是完全二叉树了。
1020
给定后序遍历和中序遍历求前序遍历，这个考408的时候就写过了，水题一道，直接上代码。
//
// Created by GreenArrow on 2020/2/21.
//
#include <iostream>
#include <queue>
using namespace std;
typedef struct node {
int data;
node *left;
node *right;
} node;
node *create(int postl, int postr, int inl, int inr, int *post, int *in) {
if (postl > postr) {
return nullptr;
}
node *root = new node;
root->data = post[postr];
int index = 0;
for (int i = inl; i <= inr; ++i) {
if (in[i] == post[postr]) {
index = i;
break;
}
}
int leftTreeNumber = index - inl;
int rightTreeNumber = inr - index;
root->left = create(postl, postl + leftTreeNumber - 1, inl, index - 1, post, in);
root->right = create(postl + leftTreeNumber, postr - 1, index + 1, inr, post, in);
return root;
}
void levelOrder(node *root) {
queue<node *> Queue;
Queue.push(root);
int index = 0;
int arr[10010];
while (!Queue.empty()) {
node *next = Queue.front();
arr[index++] = next->data;
Queue.pop();
if (next != nullptr && next->left) {
Queue.push(next->left);
}
if (next != nullptr && next->right) {
Queue.push(next->right);
}
}
for (int i = 0; i < index; ++i) {
cout << arr[i];
if (i != index - 1) {
cout << " ";
}
}
cout << endl;
}
int main() {
int n;
cin >> n;
int postOrder[n], inOrder[n];
for (int i = 0; i < n; ++i) {
cin >> postOrder[i];
}
for (int j = 0; j < n; ++j) {
cin >> inOrder[j];
}
node *root = create(0, n - 1, 0, n - 1, postOrder, inOrder);
levelOrder(root);
}
1043
这个题也是水题，就是麻烦，也就镜像哪里有点麻烦，遍历的时候先遍历右边再遍历左边就好了，代码不贴了，占篇幅。
有关图的题目：1122，1142，1150，1026，1013，1021，1034，1003，1018，1030，1087，1111
1122
这个题目能不能做出来就看你能不能记得简单回路是啥玩意了。简单回路就是在回路序列里面，除了第一个与最后一个顶点相同，其他顶点各不相同；那么哈密顿回路就再加上访问所有节点的条件。访问到所有节点，只有第一个与最后一个节点相同，中间访问的节点只访问一次就叫哈密顿回路。
那么判断的几个条件：
1.总点数是否等于n+1
2.第一项是否等于最后一项
3.相邻节点之间是否能访问
4.是否访问了所有节点
bool Hamilton(int n, int *array, int vertex_n) {
if (vertex_n + 1 != n) {
return false;
}
bool visited[vertex_n + 1];
fill(visited + 1, visited + vertex_n + 1, false);
int pre = array[1];
visited[pre] = true;
for (int i = 2; i <= n; ++i) {
if (chess[pre][array[i]] != 1 && chess[array[i]][pre] != 1 && array[i] != pre) {
return false;
}
pre = array[i];
visited[pre] = true;
}
for (int j = 1; j <= vertex_n; ++j) {
if (!visited[j]) {
return false;
}
}
if (array[1] != array[n]) {
return false;
}
return true;
}
1142
这个题目也是水题，遍历就好了，还不超时。首先遍历一遍看看序列之间的数字是否都有通路，其次遍历剩下不再序列里面的点看看能不能加入即可。
string isMaxClique(int vertex_n, int n, int *array) {
if(n == 0){
return "Not a Clique";
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (array[i] != array[j] && chess[array[i]][array[j]] == 0) {
return "Not a Clique";
}
}
}
for (int k = 1; k <= vertex_n; ++k) {
bool flag = true;
if (!visited[k]) {
for (int i = 1; i <= vertex_n; ++i) {
if (i == k) {
continue;
}
if (!visited[i]) {
continue;
}
if (chess[k][i] != 1) {
flag = false;
break;
}
}
if (flag) {
return "Not Maximal";
}
}
}
return "Yes";
}
水题一道。
1150
存在一个旅行推销员的问题，给定一个城市列表和这些城市之间的距离，问，哪条最短的路能够访问所有的城市并且最后能回到出发的城市？这是哪个NPhard的问题，也就是指示复杂度类型的问题，在运筹学研究和计算机科学理论研究上有很重要的意义。
在这个问题里，你应该要从这些城市列表里面找到一个循环，这个循环是旅行者问题的解。
输入详情：每一个输入包含一个测试样例。对于每一个案例，第一行给出两个正整数，分别是城市的数量以及边数。接下来是M行，每一个描述一条边，边的格式如下：城市1，城市2，距离。城市编号从1到N且距离为正数不超过100。接下来一行给出正整数K，路径的数量，紧接着K行描述路径，路径格式为n,C1,C2......。
输出详情：对于每一条路，打印出路径PathX:TotalDist，x是标号，totalDist是路径的总距离。差不多就这样。
这个题目读起来，很繁杂，一开始看的时候还以为他要我算出所有的简单回路。其实也就是遍历操作即可。和前面一道图的题目类似，注意一些细节操作即可，水题一道。
int getClassification(int vertex_n, int n, int *array, int &classification) {
int pre = array[0];
int sum = 0;
int result = 0;
for (int i = 1; i < n; ++i) {
if (chess[pre][array[i]] != INT_MAX) {
sum += chess[pre][array[i]];
pre = array[i];
} else {
result = INT_MAX;
classification = 2;
return result;
}
}
if (array[0] != array[n - 1]) {
classification = 2;
result = sum;
return result;
}
bool flag2 = false;
for (int j = 1; j <= vertex_n; ++j) {
if (visited[j] == 0) {
classification = 2;
result = sum;
return result;
}
if (visited[j] >= 2) {
if (j == array[0] && visited[j] > 2) {
flag2 = true;
}
if (j != array[0] && visited[j] > 1) {
flag2 = true;
}
}
}
if (flag2) {
classification = 3;
result = sum;
return result;
}
classification = 1;
result = sum;
return result;
}
1126
在图论中，一条路径如果能访问每条边一次就叫做欧几里得路径。相同的，一条欧几里得环一条起点和终点相同的欧几里得路径。在1736年，欧拉等人第一次在解决著名的七....问题是提出。如果一个图是联通图并且所有的顶点的度为偶数，那么它会存在一条欧几里得环，这样的图我们称为Eulerian。（欧几里得人？？？）如果此图恰好有两个奇数度的顶点，则所有的欧几里得路径都是从其中一个顶点出发到另一个顶点结束，只有欧几里得路径而没有欧几里得环的图称为semi-Eulerian
输入详情：每一个输入文件包含一个测试样例，每一个案例开头第一行包含两个数字，N和M，分别是顶点总数和边的总数。接下来的M行描述一条边的两端。
输出描述：第一行打印出顶点的度，按照顶点序号递增的次序，第二行输出图的类型。大概就是这样吧。
这个题目很容易瞎了眼，条件有几个，其一连通图，其二度的数量。首先可以用BFS或者DFS判断是否是联通图，然后再判断度的数量即可。先随机找一个点开始BFS，如果一次BFS完成之后所有的点都被访问了，那么这个图就是联通图，看到很多答案都是每一个点都BFS，其实没有必要，仅仅一个点进行BFS即可。
void BFS(int v) {
visited[v] = true;
for (int i = 0; i < nodes[v].size(); ++i) {
if (!visited[nodes[v][i]]) {
BFS(nodes[v][i]);
}
}
}
后面的判断degress奇偶没有很简单，也是水题。
1013
这也是一个连通图问题，给出n个城市，m条路，问你如果这个城市消失了，需要添加多少条道路才能联通。也是个水题，你把当前要消失的城市包括其有关路径都去掉，然后看看有多少个联通分量，有多少个联通分量就证明有多少个地区是分开的，然后减一就是公路的数量。一开始的做法是复制一份新的地图，把敌对城市去掉，超时了，然而我这么做是多余的，完全可以在深度遍历的时候忽略敌对城市即可。
for (int k = 0; k < K; ++k) {
fill(visited, visited + N + 1, false);
int city;
scanf("%d", &city);
visited[city] = true;
int index = 0;
for (int l = 1; l <= N; ++l) {
if (!visited[l]) {
BFS(l, city);
index++;
}
}
直接把敌对城市设置成已经访问即可，这样BFS不会去寻找已经访问的节点。
1021
如果一个图是联通的而且又没有环，那么就可以看成是一颗树。树的高度就依赖于选择的根是哪一个点。现在要求你找出高度最高的树的根，这样的根称为最深根。
输入详情：每一个输入包含一个测试样例，对于每一个样例，第一行一个正整数，表示顶点的数量，因此，顶点编号从1到N，接下来N-1行描述边。
输出详情：对于每一个测试样例，打印出深的根，如果根不是唯一，打印出所有的根，并按照升序排列。如果不是树，打印出联通分量的个数。
考查深度优先和联通分量，也是水题，BFS遍历查找最深的根，同时BFS把联通分量给找出来，因为查找最深的根和查找联通分量是可以合在一起，关键就是怎么合起来了。修改一下BFS，让其返回最深的层次：
void BFS(int v, int depth) {
visited[v] = true;
bool flag = true;
for (int i = 0; i < graph[v].size(); ++i) {
int u = graph[v][i];
if (!visited[u]) {
flag = false;
BFS(u, depth + 1);
}
}
if (flag) {
if (max_BFS < depth) {
max_BFS = depth;
}
}
}
每一次就看看当前节点的下一个节点是不是全部都访问过了，如果都访问过了那就说明到底了，对比之前的然后返回。完成后注意清空visited：
for (int j = 1; j <= N; ++j) {
fill(visited, visited + N + 1, false);
max_BFS = INT_MIN;
BFS(j, 0);
每一次完成需要清空，需要遍历所有的点找到最深的根。顺便在第一次BFS遍历的时候看看是否有访问到了所有的节点，如果没有，那就没有必要再找最深的点了，直接找联通分量了：
int max = INT_MIN;
int index_ = 0;
bool flag = false;
for (int j = 1; j <= N; ++j) {
fill(visited, visited + N + 1, false);
max_BFS = INT_MIN;
BFS(j, 0);
//cout << max_BFS << endl;
index_++;
if (!flag)
for (int i = 1; i <= N; ++i) {
if (!visited[i]) {
flag = true;
//不联通
for (int k = j + 1; k <= N; ++k) {
if (!visited[k]) {
BFS(k, 0);
index_++;
}
bool connected = true;
for (int l = 1; l <= N; ++l) {
if (!visited[l]) {
connected = false;
break;
}
}
if (connected) {
cout << "Error: " << index_ << " components" << endl;
return 0;
}
}
}
}
1034
警察找到犯罪团伙透明的方法是检查他们的手机，如果在A和B之间存在了电话联系，那么久说A和B是有关系的。关系的权重是定义了双方通话的总时长。一个帮派是指帮派成员超过两个人，并且这些人之间互相都有联系，且通话量超过既定阈值K。在每一个帮派，存在一个通话量权重最高的人，以此人为首。现在给定一些通话列表，你应该团伙以及头目。
一开始没看清题目，以为名字是三个字母相同的，从A-Z，就26个，然后写出来只对了两个点。然后做出来发现不是。我这里使用的是用向量存储图，单独存储边，如果要计算一个图的权重，遍历图中节点相加即可。这里的关系的双向关系，也就是无向图，但是通话量是单向的，在计算联通分量的时候需要按照无向图计算，计算权重的时候要按照有向图的边相加。如果按照上述做法，就麻烦了，我就是这么做的，其实A->B和B->A的权重是可以相加当成一条边计算，然后权重相加的时候只需要加一次就好了，代码优化的地方可以很多，首先就是使用的存储图的结构就可以使用矩阵，然后权重计算不用分开算，相加在一起当成是无向图。
for (int i = 0; i < n; ++i) {
string A, B;
int weight;
cin >> A >> B >> weight;
int ANumber = string2number(A), BNumber = string2number(B);
name[ANumber] = A;
name[BNumber] = B;
visited[ANumber] = false;
visited[BNumber] = false;
graphs[ANumber].push_back(BNumber);
graphs[BNumber].push_back(ANumber);
if (edges.count(ANumber) == 0) {
vector<edge> e;
e.emplace_back(BNumber, weight);
edges[ANumber] = e;
} else {
edges[ANumber].push_back(edge(BNumber, weight));
}
totalPhone[ANumber] += weight;
totalPhone[BNumber] += weight;
}
这块在输入的时候把输入的name给量化了，把所有通过节点的通话量加起来，后面要选择一个团伙的头目需要使用到。边也存储下来，数组下标就是起始点，边存储终点和权值。
void BFS(int v, int &size, int &total, vector<int> &gangs) {
visited[v] = true;
for (int i = 0; i < graphs[v].size(); ++i) {
if (!visited[graphs[v][i]]) {
gangs.push_back(graphs[v][i]);
total = addEdges(graphs[v][i], total);
size++;
BFS(graphs[v][i], size, total, gangs);
}
}
}
然后就是调用BFS了，最后还需要进行排序输出。
1003
找最短路径，算出最短路径有多少条，每一个城市会有相应的人员，经过这个城市就可以带走这些人员，在这些最短路径里面最多能带走多少人。
很明显是属于最短路径的问题，最短路径很容易，关键是如何存储下最短路径的条数。可以使用一个Num数组存储，一开始num[source] = 1，代表当前只有这一条路径，当出现了多条路径之后，也就是在更新到达路径的时候d[v]如果和之前的是相同的，num[v] += num[source]，这样其实模拟了一个乘法增长的过程，因为后面的每一条路增加，其实都是倍数增长。
void Dijikstra(int v, int n) {
fill(d, d + MAX, INT_MAX);
fill(visited, visited + MAX, false);
fill(w, w + MAX, 0);
fill(num, num + MAX, 0);
w[v] = people[v];
num[v] = 1;
d[v] = 0;
for (int i = 0; i < n; ++i) {
int min = INT_MAX;
int u = -1;
for (int j = 0; j < n; ++j) {
if (!visited[j] && min > d[j]) {
min = d[j];
u = j;
}
}
if (u == -1)
return;
visited[u] = true;
for (int k = 0; k < n; ++k) {
if (!visited[k] && chess[u][k] != INT_MAX) {
if (d[k] > d[u] + chess[u][k]) {
d[k] = d[u] + chess[u][k];
w[k] = w[u] + people[k];
num[k] = num[u];
} else if (d[k] == d[u] + chess[u][k]) {
num[k] += num[u];
if (w[u] + people[k] > w[k]) {
w[k] = w[u] + people[k];
}
}
}
}
}
}
就是调用算法即可，如果还需要求路径，只需要用一个vector即可。
1018
大概就是说有几个车站，当容量为一半的时候是最佳状态，现在需要去某一个车站，问你那一条路径是路径最短，填补车辆最少，回收车辆最少。看上去好像是最短路径，但是事实上这是一个深度搜索的问题，最短路径没有办法保证送回和送出的数据是全局最优的。
void DFS(int s, int end, int tempSend, int tempBack, int tempDis) {
visited[s] = true;
tempPath.push_back(s);
if (s == end) {
if (minDis > tempDis) {
path = tempPath;
minDis = tempDis;
minSend = tempSend;
minBack = tempBack;
} else if (minDis == tempDis) {
if (minSend > tempSend) {
path = tempPath;
minSend = tempSend;
minBack = tempBack;
} else if (minSend == tempSend) {
if (minBack > tempBack) {
path = tempPath;
minSend = tempSend;
minBack = tempBack;
}
}
}
return;
}
for (int i = 1; i <= n; ++i) {
if (!visited[i] && chess[s][i] != INT_MAX) {
int temp = bikes[i] - capacity / 2;
int tempB = tempBack;
int tempS = tempSend;
if (temp >= 0) {
tempB += temp;
} else {
if (temp + tempB < 0) {
tempS -= (temp + tempB);
tempB = 0;
} else {
tempB = (temp + tempB);
}
}
DFS(i, end, tempS, tempB, tempDis + chess[s][i]);
tempPath.pop_back();
visited[i] = false;
}
}
}
有点复杂，用Dijiskra也只能有25分，主要容易搞混的其实就是回收和放出那里：
int temp = bikes[i] - capacity / 2;
int tempB = tempBack;
int tempS = tempSend;
if (temp >= 0) {
tempB += temp;
} else {
if (temp + tempB < 0) {
tempS -= (temp + tempB);
tempB = 0;
} else {
tempB = (temp + tempB);
}
}
先算出当前点需要多少，如果不需要了还多出盈余，那就加上前面需要送回的；如果缺了，就看看以往需要送回的能不能填补，如果能填补，那么减去已经填补的，如果不能填补，那么就要继续送剩下的。
1030
给出一张旅行者地图，地图给出城市之间的距离已经花费，现在要求你写出程序帮助旅行者决定最短的路径，如果路径最短并非唯一，则给出最小花费，次最小花费的最短路径保证唯一。
输入详情：每一个输入包含了一个测试样例，每一个样例由4个正整数开始，分别是城市数量，告诉公路的数量，起始点和目的地。接下来M行分别就是边的属性。
输出详情：对于每一个测试样例，输出最短路径，路径距离，路径花费。
这个题目相比上面一题要简单不少，就是一个条件而已:
void Dijiskra(int s, int n) {
fill(visited, visited + MAX, false);
fill(d, d + MAX, edge(INT_MAX, INT_MAX));
d[s].distance = 0;
d[s].cost = 0;
for (int i = 0; i < n; ++i) {
int u = -1;
int min = INT_MAX;
for (int j = 0; j < n; ++j) {
if (!visited[j] && d[j].distance < min) {
min = d[j].distance;
u = j;
}
}
if (u == -1) {
return;
}
visited[u] = true;
for (int k = 0; k < n; ++k) {
if (!visited[k] && map[u][k].distance != INT_MAX) {
if (d[k].distance > d[u].distance + map[u][k].distance) {
d[k].distance = d[u].distance + map[u][k].distance;
d[k].cost = d[u].cost + map[u][k].cost;
path[k] = u;
} else if (d[k].distance == d[u].distance + map[u][k].distance) {
if (d[k].cost > d[u].cost + map[u][k].cost) {
d[k].distance = d[u].distance + map[u][k].distance;
d[k].cost = d[u].cost + map[u][k].cost;
path[k] = u;
}
}
}
}
}
}
1087
说是有几个城市，城市之间存在路径，通过路径需要花费，而每经过一个城市就可以获得这个城市的快乐值，问路径最短并且能得到最大快乐值的是那一条路。
这个题目比上上题和上上上题都要简单，和上一题难度差不多，其实就是最短路径加上一点条件而已。
void Dijiskra(int s, int n) {
fill(visited, visited + MAX, false);
fill(d, d + MAX, INT_MAX);
fill(happy_total, happy_total + MAX, 0);
fill(num, num + MAX, 0);
num[s] = 1;
d[s] = 0;
for (int i = 0; i < n; ++i) {
int u = -1;
int min = INT_MAX;
for (int j = 0; j < n; ++j) {
if (!visited[j] && d[j] < min) {
min = d[j];
u = j;
}
}
visited[u] = true;
if (u == -1)
return;
for (int k = 0; k < n; ++k) {
if (!visited[k] && chess[u][k] != INT_MAX) {
if (d[k] > d[u] + chess[u][k]) {
d[k] = d[u] + chess[u][k];
happy_total[k] = happy_total[u] + name[k].happy;
num[k] = num[u];
path[k] = u;
} else if (d[k] == d[u] + chess[u][k]) {
num[k] += num[u];
if (happy_total[k] < happy_total[u] + name[k].happy) {
happy_total[k] = happy_total[u] + name[k].happy;
path[k] = u;
}
}
}
}
}
}
1111
这个题目和上一题很类似，两个最短路径就好了，当然了也可以合成一个。首先一个是求路程花费最短的，其次是求时间最短，如果路径最短有多条，那就把时间最短的选出来；如果时间最短的有多条，把经过城市最短的选出来。城市最短可以用一个数组记录，每更新一次，就继承前一点的值加1。
void Dijiskra_t(int s, int n) {
fill(t, t + MAX, INT_MAX);
fill(visited_t, visited_t + MAX, false);
fill(size_time, size_time + MAX, 0);
size_time[s] = 1;
t[s] = 0;
for (int i = 0; i < n; ++i) {
int u = -1;
int min = INT_MAX;
for (int j = 0; j < n; ++j) {
if (!visited_t[j] && t[j] < min) {
u = j;
min = t[j];
}
}
visited_t[u] = true;
for (int k = 0; k < n; ++k) {
if (!visited_t[k] && chess[u][k].time != INT_MAX) {
if (t[k] > t[u] + chess[u][k].time) {
t[k] = t[u] + chess[u][k].time;
size_time[k] = size_time[u] + 1;
path_t[k] = u;
} else if (t[k] == t[u] + chess[u][k].time) {
if (size_time[k] > size_time[u] + 1) {
size_time[k] = size_time[u] + 1;
path_t[k] = u;
}
}
}
}
}
}
DFS，BFS：1004，1021，1018（这两题图论已写），1076，1079，1094，1103，1027，1130
1004
规定了根节点是1号，让你找出每一层的叶子节点。这个题目也是个水题，但是有些小坑，稍不注意就拿不了30。可以用BFS也可以用DFS，我是用BFS做的，因为直接在树的结构里面加上层次属性就可以了。测试点2有一个小坑，当输入1 0的时候要输出1，因为在BFS里面我的最大层次是初始-1，如果输入1 0那么就不会进入到while循环里面，结果什么都不输出了，所以把最大层次初始化为0就好；还有当n=0的时候不做处理，什么都不输出，需要直接return 0；
int levelOrder(treeNode *root) {
int max = 0;
queue<treeNode *> Queue;
Queue.push(root);
root->depth = 0;
while (!Queue.empty()) {
treeNode *cur = Queue.front();
Queue.pop();
if (!cur->children.size())
depth[cur->depth]++;
for (int i = 0; i < cur->children.size(); ++i) {
cur->children[i]->depth = cur->depth + 1;
Queue.push(cur->children[i]);
if (cur->children[i]->depth > max) {
max = cur->children[i]->depth;
}
}
}
return max;
}
1076
这个题目，一开始看错题目了，把粉丝和up主的关系看反了，第一行3 2 3 4应该是2 3 4号用户关注了1才对。这个题目其实也很简单，就是广度优先就好了：
int BFS(int s, int L, vector<int> graph[MAX]) {
fill(visited, visited + MAX, false);
fill(layer, layer + MAX, 0);
int number = 0;
layer[s] = 0;
visited[s] = true;
queue<int> Queue;
Queue.push(s);
while (!Queue.empty()) {
int cur = Queue.front();
Queue.pop();
if (layer[cur] <= L && cur != s) {
number++;
}
for (int i = 0; i < graph[cur].size(); ++i) {
int v = graph[cur][i];
if (!visited[graph[cur][i]]) {
Queue.push(graph[cur][i]);
layer[graph[cur][i]] = layer[cur] + 1;
visited[graph[cur][i]] = true;
}
}
}
return number;
}
1079
这个题目和之前的有一道类似，这里还是用DFS，水题一道，直接DFS遍历就好了。需要注意，根节点是不唯一的，可能有多个根节点，需要把所有可能的根节点集中一起分开遍历，最后还有一些内存问题，这里说N是小于一万，然而我开一万段溢出，开十万才行。
void DFS(treeNode *root, double price, double r) {
if (number[root->val] != -1 && root->children.size() == 0) {
total += number[root->val] * price;
return;
}
for (int i = 0; i < root->children.size(); ++i) {
DFS(root->children[i], price * ((100 + r) / 100), r);
}
}
1094
前面有过类似的，要你求最多孩子的层数以及孩子数量。水题一道，层次遍历就好了，或者深度搜索也可以。
void BFS(TreeNode root) {
root->depth = 1;
queue<TreeNode> Queue;
Queue.push(root);
while (!Queue.empty()) {
TreeNode cur = Queue.front();
Queue.pop();
depth[cur->depth]++;
if (max_ < depth[cur->depth]) {
max_ = depth[cur->depth];
maxDepth = cur->depth;
}
for (int i = 0; i < cur->children.size(); ++i) {
Queue.push(cur->children[i]);
cur->children[i]->depth = cur->depth + 1;
}
}
}
1103
这个题目第一眼觉得是水题，写完了才发现不对劲，很明显是DFS，不过关键还是要确定上下界。把所有p次方的数字存储在一个数组里面，然后计算上界，因为底数最小是1，那么最大就是n - (k-1)大小了，所以底数最大就是对(n-(k-1))开p次方：
void init(int n, int p) {
for (int i = 0; i <= n; i++) {
int temp = kpow(i, p);
if (temp > n) {
break;
}
arr[i] = temp;
}
double num = (n - (K - 1));
double kDouble = P;
tempMax = pow(num, 1 / kDouble);
}
接着就是DFS，倒序开始，找到那个和最大的就好了，没必要再进行比较了。
void DFS(int i, int sumPre, int depth, int tempSum) {
if (depth == K) {
if (sumPre == N) {
if (sum < tempSum) {
sum = tempSum;
result.assign(numString.begin(), numString.begin() + K);
}
}
return;
}
if (sumPre >= N || depth > K) {
return;
}
for (; i >= 1; --i) {
if (sumPre + arr[i] <= N) {
numString[depth] = i;
DFS(i, sumPre + arr[i], depth + 1, tempSum + i);
}
}
}
如果递归层数到了k，那么就说明已经有k个数了，查看是否等于n，并且和是否大于result。如果没到k层就大于等于n，那就不用看了，直接回去。否则继续DFS。然而超时了，找了一天都不知道要怎么改，总感觉没问题：
//
// Created by GreenArrow on 2020/3/24.
//
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> result;
int sum = -1;
vector<int> numString(10001, 0);
int arr[10010];
int N, K, P;
int kpow(int x, int y) {
int ret = x;
while (--y) {
ret *= x;
}
return ret;
}
void DFS(int i, int sumPre, int depth, int tempSum) {
if (depth == K) {
if (sumPre == N) {
if (sum < tempSum) {
sum = tempSum;
result.assign(numString.begin(), numString.begin() + K);
}
}
return;
}
if (sumPre >= N || depth > K) {
return;
}
for (; i >= 1; --i) {
if (sumPre + arr[i] <= N) {
numString[depth] = i;
DFS(i, sumPre + arr[i], depth + 1, tempSum + i);
}
}
}
int tempMax = 0;
void init(int n, int p) {
for (int i = 0; i <= n; i++) {
int temp = kpow(i, p);
if (temp > n) {
break;
}
arr[i] = temp;
}
double num = (n - (K - 1));
double kDouble = P;
tempMax = pow(num, 1 / kDouble);
}
int main() {
cin >> N >> K >> P;
if (N == K) {
cout << N << " = ";
for (int i = 0; i < K; ++i) {
cout << 1 << "^" << P;
if (i != K - 1) {
cout << " + ";
}
}
return 0;
}
init(N, P);
for (int i = tempMax; i >= 1; --i) {
DFS(i, 0, 0, 0);
}
if (result.size() == 0) {
cout << "Impossible";
return 0;
}
cout << N << " = ";
for (int j = 0; j < K; ++j) {
cout << result[j] << "^" << P;
if (j != K - 1) {
cout << " + ";
}
}
}
哭了都，最后还是仿造别人的过了，但是查看了一下，思路和优化点都一样。
1127
这个题目也是一个水题，我的做法可能稍微有点麻烦，是把每一层的数目记录下来，然后按照不同层数查看是否需要扭转次序，方法很笨，但是还是过了。看到柳神有更好的做法，感兴趣可自己搜寻一二。
关键点还是在构建树这里，中序遍历和后续遍历构建一棵树这些题目见多不怪了，只要下标数对了就好写，层次遍历变形一下即可。
TreeNode create(int inL, int inR, int postL, int postR, vector<int> inOrder, vector<int> postOrder) {
TreeNode root = nullptr;
root = new treeNode;
if (inL > inR) {
return nullptr;
}
if (inL == inR) {
root->val = inOrder[inL];
root->right = root->left = nullptr;
return root;
}
int rootNum = postOrder[postR];
int index = -1;
for (int i = inL; i <= inR; ++i) {
if (inOrder[i] == rootNum) {
index = i;
break;
}
}
int leftNum = index - inL;
root->val = rootNum;
root->left = create(inL, index - 1, postL, postL + leftNum - 1, inOrder, postOrder);
root->right = create(index + 1, inR, postL + leftNum, postR - 1, inOrder, postOrder);
return root;
}
void zlevel(TreeNode root) {
queue<TreeNode> Queue;
root->depth = 1;
Queue.push(root);
while (!Queue.empty()) {
TreeNode cur = Queue.front();
Queue.pop();
if (levelOrder.size() < cur->depth + 1) {
vector<int> newDepth;
newDepth.push_back(cur->val);
levelOrder.push_back(newDepth);
} else {
levelOrder[cur->depth].push_back(cur->val);
}
if (cur->left) {
cur->left->depth = cur->depth + 1;
Queue.push(cur->left);
}
if (cur->right) {
cur->right->depth = cur->depth + 1;
Queue.push(cur->right);
}
}
}
1130
按照中序遍历就好了，水题一道，没什么好说的，注意一些特殊情况就好了。
void inOrder(TreeNode root, TreeNode parent) {
if (root) {
if ((root->left != nullptr || root->right != nullptr) && root != parent)
result += "(";
inOrder(root->left, parent);
result += root->val;
inOrder(root->right, parent);
if ((root->left != nullptr || root->right != nullptr) && root != parent)
result += ")";
}
}
中序遍历注意一下即可，只要是等于根的，那就不用输出括号。其余的创建树之前的题目都写过了。
