本题关键在于如何实现克鲁斯卡尔算法。该算法需要将边从小到大进行排序，每次选出不会成环且最小的边，直到边数为节点数减去1，意味着最小生成树生成完成 /*请计算最小的公路总长度。输入描述：测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离， 每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。当N为0时，输入结束，该用例不被处理。 输出描述：对每个测试用例，在1行里输出最小的公路总长度。 输入： 3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 ...

https://www.acwing.com/problem/content/3412/思路：本题需要判断一个图是否为树，这需要我们判断三个要素：1.一个树的边数应该比节点数少12.一个树的节点入度应该小于等于2，且只有一个入度为0的节点即根节点 3.从根节点到任意节点有且仅有一条唯一路线1我们使用两个计数变量edgecount和vertexcount解决，2我们用入度数组和访问数组解决，3我们用并查集解决，并维护一个布尔型变量记录当前是否判断可以成树注意点：1.每次完成后需要将数组变量进行初始化防止影响下一步2.将布尔型变量修改后不需要return而是应该继续循环直到所有数据都处理完成 /*...

写好并查集的查和并两个模块后，我们考虑，每次新输入的边代表着两个节点直接有关联，我们只需要把其中一个节点置为另一个节点的子节点，就可以维护一个并查集结构。直到遍历结束，此时用一个整型变量记录剩余并查集数量。代表着类似于自治域的不连通的模块，我们只需要在这n个模块之间修n-1条路就可以使其联通，故打印n-1 #include <bits/stdc++.h> using namespace std; int father[1010]; int setcount;//记录剩余未进行合并操作的子集 void initialize(int n) { for (int i = 0; ...

简单的数组建树＋中序遍历 #include <bits/stdc++.h> using namespace std; struct TreeNode { char data; TreeNode* left; TreeNode* right; }; TreeNode* BuileTree(int& i, char arr[]) { char c = arr[i]; i++; if (c == '#') { return NULL; } else { TreeNode* pNew = new...

#include <bits/stdc++.h> using namespace std; int main() { int n,m; priority_queue<int> Myqueue; scanf("%d",&n); int wpl=0; for(int i=0;i<n;i++){ scanf("%d",&m); Myqueue.push(-1*m); } while(Myqueue.size()>=2){...

运用优先队列，可以将哈夫曼树序列的数字从小到大排列（借助负数取反技巧)当队列中至少有两个元素的时候，取出队列头的两个元素相加，权重和加上这个数之后，把这个数重新压入优先队列，重复操作。 #include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d", &n); priority_queue<int> Myqueue; for (int i = 0; i < n; i++) { int m; ...

本题思路很简单，借助重载运算符和优先队列，我们可以很容易的将输入的复数进行从大到小排列并输出，每次根据具体情况决定打印顺序即可。主要应该关注重载运算符和构造函数的使用，以及优先队列隐含的数据类型必须支持小于运算符的思想。重载运算符也是把大根堆变成小根堆的方式之一 #include <bits/stdc++.h> using namespace std; struct Complex { //结构体定义，复数可表示为a+bi int a; int b; Complex(int _a,int _b){ //构造函数 a = _a; ...

本题思路是在于，根据给定的序列先插入一棵二叉搜索树，随后的序列中，如果有序列的先序和中序序列与其完全一致，则证明后续建树的二叉搜索树和自己一致。需要三个函数：1.建树函数，参数为当前根节点和将要插入的数值2.中序遍历函数，参数为根节点的指针，返回字符串3.先序遍历函数，参数为根节点的指针，返回字符串注意！！！建树函数的参数根节点需要用引用符号，因为会直接修改原root的值作为下一个参数传入，不然BST树会一直为空 /*判断两序列是否为同一二叉搜索树序列 输入描述： 开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。 接下去一行是一个序列，序列长度小于...

https://www.acwing.com/problem/content/3388/思路：本题难点在于，如何确保所有可能的子序列都被遍历到，还要保证不能重复遍历。相比于深度优先，广度优先一层一层来的思想更好的保证了这一基本原则，把每一经过旋转的子序列看作是下一层，同时维护一个数据结构记录是否被访问即可解法1.读入数据，若数据小于4直接返回-1；若大于，则维护一个无序map记录是否被访问，一个辅助队列进行广度优先遍历，一个cur字符串记录当前的子序列。将原始字符串压入栈中2.当栈不为空时，先弹出栈顶字符串检查是否有2012，语法采用cur.find("2012" )!= ...

https://www.acwing.com/problem/content/3702/思路：本题明面上是求树的高度，但却给出了类似于邻接表的存储方式，类似于一张无环图，但完全不知道节点之间的父子关系。考虑两种搜索方式，层序遍历可以严格保证先父后子的遍历顺序，故采用层序遍历。同时设置一个辅助数组来记录节点是否被访问过，如有，则证明是当前节点的父辈。做法：分别定义一个vector<vector<int>>型的邻接表结构，一个存储遍历顺序的队列toVisit，一个记录是否访问和最大长度的数组distance，循环访问邻接表。初始将固定的根节点压入队列。当队列不为空时：1.读...

https://www.acwing.com/problem/content/3445/思路：对背包dp模板稍加修改，注意转移方程和初始化的方法即可解法：新建dp数组dp[i][j]，表示用i个物品凑齐j体积的方法总数，按顺序读取N和物品体积序列之后:1.将dp数组的dp[0][0]置为02.用i和j进行遍历a.对于每一个dp[i][j]，首先先把dp[i-1][j]（代表少一件凑齐j的方法）赋值给他，意味着这件物品不能使用，故保留上一种方法的数量b.判断，如果此时可以使用这个物品，dp[i][j]就要再加上用i-1件物品凑齐j-arr[i]的方法c.直到遍历结束，打印dp[n][40]即可 ...

https://www.acwing.com/problem/content/3448/想法：套二维数组dp公式，先找到小问题及转移方程解法：将题目所述数据读入整型变量c，n和价格数组p[]以及评价数组v[]；1.新建一个大小为1001*102的dp数组dp[i][j]，每个元素表示：在预算为j元的时候，考虑从0到j号菜品组合中评价最高的评分2.双for循环遍历，注意i是从1到c，j是从1到n（上限取等号）3.对于某个i，遍历的每一个j：a.检查j菜品是否超出价格i，若超出则将上一个菜品对应的评分（dp[i][j-1]）赋值给当前评分（dp[i][j]）b.若没有超出，则选择上一个菜品对应的评...

https://www.acwing.com/problem/content/3511/本题主要思路与上题类似，头文件只用到了一部分我懒得调所以都粘上来了修改的地方：由于需要连续的公共子序列，且只要小写字母不要数字，故相比（一）做出如下改动1.if语句条件改为判断此时是否为小写字母&&两字符串元素是否相等2.满足if语句则仍将该节点值置为上一节点的值加一，同时判断该节点值是否超过由整型变量currentmax记录的最大值，若超过则更新currentmax2.若不满足if语句则将该节点值置为0（为了保证连续子串的性质） #include <bits/stdc++.h>...

思路：本题需要处理两个字符串的最长公共子序列（可以不连续），故考虑使用一个二维的dp数组，存储遍历两个字符串时每个子问题对应的最长公共子序列长度解法：用两个变量i和j分别遍历两字符串，不妨对于每个i，都遍历j。对于此时的dp[i][j]，如果此时两字符串中i和j分别指向的元素相等，立刻将dp[i][j]赋值为dp[i-1][j-1]+1；反之，则在该节点的上方和左方选择较大的节点值修改进dp[i][j]。最后输出dp[n][m]即可 #include <iostream> #include <cstdio> #include <vector> #includ...