思路：构造最小生成树，即保证所有顶点连通（间接也可以）+边的权值最小。可用克鲁斯克拉算法求生成树：每次选权值最小的边，判断若边所在的两个顶点不连通则加入树中，否则跳过该边，一直到树构建完成（特征是边数=顶点个数-1）。 #include <cstring> #include<stdio.h> #include<vector> #include<algorithm> using namespace std; int father[1010]; //初始化 void Initfun(int n) { for (int i = 1; i < n;...

题目链接思路：依次把输入结点-结点加入集合中（形成1棵树），判断是否标记false：（注意是仅标记，非立即终止树的构造）1.有环不行：用并查集判断，在已连通的2顶点（处于同一集合，根一样），加入一条边则成环2.多个入边不行：用一个数组记录各个顶点入度3.不相连不行：无环的连通性：边数=结点个数-1ps：呜呜呜呜呜呜我以后一定认真写if-else，搞了半天没accepted，逻辑检查了几遍发现是main里面第二个if后面没写else，导致本来else中的代码也默认执行了！ #include<stdio.h> #include<vector> #include<alg...

思路：考察并查集的基本操作，根据题目要求构建并查集，初始化并查集个数为城镇个数，依次输入道路合并，最后需要建设的道路数目为并查集个数-1：合并到最后只有1个并查集，则说明集合内结点相互连通，不用建路；合并到最后只有2个并查集，之间要建1条路才连通；合并到最后只有3个并查集，之间要建2条路才连通； #include <cstring> #include<stdio.h> #include<vector> #include<algorithm> using namespace std; int father[1010]; int setCnt;//记...

题目链接题目:把含若干数字的数组任意划分成两个子数组，使得两个子数组的和相差最小。本题采用3种解法，最后一种ac。解法一：动态规划（数组和不大时可以采用，否则容易超时）思路：设数组总和为sum，目标是找到一个子数组使得子数组和尽可能<=sum/2，这样两个数组和若相等，则和相差最小是0。对于每一个数组中数字，都要更新dp数组：如果之前能凑出vec[i](数组元素），那么现在有了j，你就能凑出vev[i]+j了（前提是 vev[i]+j 不超过 target） #include<stdio.h> #include<vector> #include<algori...

8皇后问题：将8 个皇后放置在8*8的棋盘上，并且使得皇后彼此之间不能攻击。皇后彼此不能相互攻击：指的是任何两个皇后都不能处于同一条横线、纵线或者斜线上。返回解决方案个数。思路：逐行放置皇后，每次尝试将皇后放在当前一行的某一列，判断是否不互相攻击，，冲突则跳过该列；如果不冲突就在该列放置皇后，并且递归处理下一个位置的皇后，最后注意撤销当前选择的列，以便尝试其他可能的列。 #include<stdio.h> #include<vector> using namespace std; vector<vector<int>> queeenVec;//结...

思路：采用广度优先遍历，每次从队列头拿出一个字符串，检查，然后生成所有可能的“下一代”字符串放回队列尾部这样，先入队的（移动步数少的）一定会先被处理，保证了找到的第一个解就是步数最少的解。存放待处理的字符串——队列；找子串——find；记录哪些字符串已经处理过了（防止走回头路，比如从 A 变到 B，又从 B 变回 A）——map； #include<iostream> #include<queue> #include<unordered_map>//时间效率为o(1)，比map高 #include<string> using namespace ...

题目链接通过广度优先搜索（BFS）来求解树的高度，其核心思想是将“求树的高度”转化为“求根节点到所有其他节点的最大距离”。 #include<stdio.h> #include<string> #include<queue> using namespace std; int main() { int n, m; scanf("%d%d", &n, &m);//输入结点个数，根结点编号 //用邻接表存储边和结点，邻接表的本质是二维数组 vector<vector<int>>tree(n + 1);//...

题目链接要求输出哈夫曼树的带权路径长度，优先队列默认是大根堆排序，若元素取反存入就是小根堆存储，每次取出最小的两个数相加，结果再存入优先队列比较，直到队列中仅剩一个元素，即为wpl的相反数。 #include<stdio.h> #include<string> #include<queue> using namespace std; int main() { int N,data; priority_queue<int> myqueue; scanf("%d", &N); for (int i = 0; i < ...

优先队列：默认大根堆，重载运算符的比较规则有点绕 #include<stdio.h> #include<string> #include<queue> using namespace std; struct Complex { int a; int b; Complex(int a_, int b_) { a = a_; b = b_; } }; //因为默认的比较规则只能比较int和double类型，故自定义运算符，重载 < 号 //注意：(a<b)为真或(a>b)为真,都是a（左边那个）输了，谁被判定为输（返回 true），谁就要被挤到...

按题目要求改写比较规则，利用sort排序动态数组 #include<stdio.h> #include<vector> #include<algorithm> using namespace std; //修改比较规则 bool compare(int l,int r){ //不交换的情况返回真 //奇数在前偶数在后不交换 //奇数l>奇数r不交换 //偶数l<偶数r不交换 if((l%2!=0)&&(r%2==0)){ return true; }else if((l%2!=0)&&(r%2!=0)&&a...

#include<stdio.h> #include<vector> using namespace std; //判断是否相等,注意& bool isSame(vector<int> &vec) { for (int i = 0; i < vec.size(); i++) { if (vec[0] != vec[i])return false; } return true; } //分糖果 void fentangguo(vector<int> &vec, vector<int> &vec2) ...

#include<stdio.h> #include<vector> #include<math.h> using namespace std; int yinziSum(int n){ int sum=0; for(int i=1;i<n;i++){ if(n%i==0)sum+=i; } return sum; } int main(){ vector<int> yinsu; vector<int> wansu; for(int i=2;i<=60;i++){ if(i==yinziSum(i)){ wansu.pus...

#include<stdio.h> #include<vector> using namespace std; //注意区间可能有重叠 int main(){ int L,M; int begin,end,cnt=0; scanf("%d %d\n",&L,&M); vector<int> vec(L); while(M){ M--; scanf("%d %d\n",&begin,&end); for(int i=begin;i<=end;i++){ vec[i]=1; } } i...

一个中序遍历序列+（层序/前序/后序）中任意一个序列可以唯一确定一颗树形。思路：先建好二叉排序树，再比较前序和中序序列是否都一致。 #include<stdio.h> #include<iostream> #include<string> #include<vector> using namespace std; typedef struct LNode { char data; struct LNode* left; struct LNode* right; } TreeNode, *BiTree; //建二叉排序树 void insertBS...