Prim算法和Kruskal算法都是从连通图中找出最小生成树的经典算法。从策略上来说，Prim算法是直接查找，多次寻找邻边的权重最小值，而Kruskal是需要先对权重排序后查找的。
所以说，Kruskal在算法效率上是比Prim快的，因为Kruskal只需一次对权重的排序就能找到最小生成树，而Prim算法需要多次对邻边排序才能找到。
首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出最小生成树中各结点权重最小的边，并加到最小生成树中。（加入之后如果产生回路了就要跳过这条边，选择下一个结点。）当所有的结点都加入到最小生成树中后，就找出了这个连通图的最小生成树。
Kruskal算法在找最小生成树结点之前，需要对权重从小到大进行排序。将排序好的权重边依次加入到最小生成树中，（如果加入时产生回路就跳过这条边，加入下一条边）。当所有的结点都加入到最小生成树中后，就找到了这个连通图的最小生成树。
01背包问题的动态规划解法递归方程为：
|
1 2 |
当 j >= wi 时, m(i, j) = max { m(i-1, j), m(i-1, j-wi) + vi }; 当 j < wi 时， m(i, j) = m(i-1, j) |
此时时间复杂度为O(n)。
使用回溯法解决01背包问题时，若可选物品为n个，则其解空间由长度为n的0-1向量组成。
此时时间复杂度为O(n2^n)。
使用分支限界法时，首先要对数据进行预处理，将物品重量价值按从小到大排列。分治限界法的缺点是占用内存大，效率不高。
时间复杂度为O(2^n)。
Snagit截图时候鼠标变大太大的解决方法：
将Snagit的Capture Preference – Capture – Capture Settings中的Capture cursor关闭
Bartender 2不能隐藏百度云同步盘图标的解决方法：
The “Hamilton cycle problem” is to find a simple cycle that contains every vertex in a graph. Such a cycle is called a “Hamiltonian cycle”.
In this problem, you are supposed to tell if a given cycle is a Hamiltonian cycle.
Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers N (2< N <= 200), the number of vertices, and M, the number of edges in an undirected graph. Then M lines follow, each describes an edge in the format “Vertex1 Vertex2”, where the vertices are numbered from 1 to N. The next line gives a positive integer K which is the number of queries, followed by K lines of queries, each in the format:
n V1 V2 … Vn
where n is the number of vertices in the list, and Vi‘s are the vertices on a path.
Output Specification:
For each query, print in a line “YES” if the path does form a Hamiltonian cycle, or “NO” if not.
Sample Input:
6 10
6 2
3 4
1 5
2 5
3 1
4 1
1 6
6 3
1 2
4 5
6
7 5 1 4 3 6 2 5
6 5 1 4 3 6 2
9 6 2 1 6 3 4 5 2 6
4 1 2 5 1
7 6 1 3 4 5 2 6
7 6 1 2 5 4 3 1
Sample Output:
YES
NO
NO
NO
YES
NO
题目大意：给出一个图，判断给定的路径是不是哈密尔顿路径
分析：1.设置falg1 判断节点是否多走、少走、或走成环
2.设置flag2 判断这条路能不能走通
3.当falg1、flag2都为1时是哈密尔顿路径，否则不是
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <iostream> #include <set> #include <vector> using namespace std; int main() { int n, m, cnt, k, a[210][210] = {0}; cin >> n >> m; for(int i = 0; i < m; i++) { int t1, t2; scanf("%d%d", &t1, &t2); a[t1][t2] = a[t2][t1] = 1; } cin >> cnt; while(cnt--) { cin >> k; vector<int> v(k); set<int> s; int flag1 = 1, flag2 = 1; for(int i = 0; i < k; i++) { scanf("%d", &v[i]); s.insert(v[i]); } if(s.size() != n || k - 1 != n || v[0] != v[k-1]) flag1 = 0; for(int i = 0; i < k - 1; i++) if(a[v[i]][v[i+1]] == 0) flag2 = 0; printf("%s",flag1 && flag2 ? "YES\n" : "NO\n"); } return 0; } |
An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.
Now given a sequence of insertions, you are supposed to output the level-order traversal sequence of the resulting AVL tree, and to tell if it is a complete binary tree.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (<= 20). Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.
Output Specification:
For each test case, insert the keys one by one into an initially empty AVL tree. Then first print in a line the level-order traversal sequence of the resulting AVL tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line. Then in the next line, print “YES” if the tree is complete, or “NO” if not.
Sample Input 1:
5
88 70 61 63 65
Sample Output 1:
70 63 88 61 65
YES
Sample Input 2:
8
88 70 61 96 120 90 65 68
Sample Output 2:
88 65 96 61 70 90 120 68
NO
分析：这道题实际上考察AVL树和层序遍历两个知识点～～
判断是不是完全二叉树，就看在出现了一个孩子为空的结点之后是否还会出现孩子结点不为空的结点，如果出现了就不是完全二叉树。
AVL树一共有四种情况，这里我把发现树不平衡的那个结点叫做A结点，A发现树不平衡的情况有四种：
新来的结点插入到A的左子树的左子树
新来的结点插入到A的左子树的右子树
新来的结点插入到A的右子树的左子树
新来的结点插入到A的右子树的右子树
发现不平衡时就需要处理，第1种情况只要简单的右旋，第4种情况只需左旋一下，第2种情况需要先对A的左子树左旋一下，然后对A右旋，同理第3种情况需要对A的右子树右旋一下，然后对A左旋就可以啦～～～
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
#include <iostream> #include <vector> #include <queue> using namespace std; struct node { int val; struct node *left, *right; }; node* leftRotate(node *tree) { node *temp = tree->right; tree->right = temp->left; temp->left = tree; return temp; } node* rightRotate(node *tree) { node *temp = tree->left; tree->left = temp->right; temp->right = tree; return temp; } node* leftRightRotate(node *tree) { tree->left = leftRotate(tree->left); return rightRotate(tree); } node* rightLeftRotate(node *tree) { tree->right = rightRotate(tree->right); return leftRotate(tree); } int getHeight(node *tree) { if (tree == NULL) return 0; int l = getHeight(tree->left); int r = getHeight(tree->right); return max(l, r) + 1; } node* insert(node *tree, int val) { if (tree == NULL) { tree = new node(); tree->val = val; }else if (tree->val > val) { tree->left = insert(tree->left, val); int l = getHeight(tree->left), r = getHeight(tree->right); if (l - r >= 2) { if (val < tree->left->val) tree = rightRotate(tree); else tree = leftRightRotate(tree); } } else { tree->right = insert(tree->right, val); int l = getHeight(tree->left), r = getHeight(tree->right); if (r - l >= 2) { if (val > tree->right->val) tree = leftRotate(tree); else tree = rightLeftRotate(tree); } } return tree; } int isComplete = 1, after = 0; vector<int> levelOrder(node *tree) { vector<int> v; queue<node *> queue; queue.push(tree); while (!queue.empty()) { node *temp = queue.front(); queue.pop(); v.push_back(temp->val); if (temp->left != NULL) { if (after) isComplete = 0; queue.push(temp->left); } else { after = 1; } if (temp->right != NULL) { if (after) isComplete = 0; queue.push(temp->right); } else { after = 1; } } return v; } int main() { int n, temp; scanf("%d", &n); node *tree = NULL; for (int i = 0; i < n; i++) { scanf("%d", &temp); tree = insert(tree, temp); } vector<int> v = levelOrder(tree); for (int i = 0; i < v.size(); i++) { if (i != 0) printf(" "); printf("%d", v[i]); } printf("\n%s", isComplete ? "YES" : "NO"); return 0; } |