Programming VIP

A Graph is composed of a finite non empty set of vertices and a set of edges between vertices. It is usually expressed as: G(V,E), where g represents a Graph, V is the set of vertices in Graph G, and E is the set of edges in Graph G. Graph is a more complex data structure than linear table and tree. In the graph structure, the relationship bet ...

February 06, 2022, 17th 1. Title Link: P2542 [AHOI2005] Route Planning Ideas: L C T LCT LCT Plus Set Solution, Time Complexity O ( ...

1, AcWing 1140 Shortest network [Title Description] Farmer John was elected mayor of his town! One of his campaign promises is to build an Internet in the town and connect to all farms. John has arranged a high-speed network line for his farm. He wants to share this line with other farms. What's the number of John's farm ...

introduce Tree Isomorphism: if two trees have the same shape, they are called isomorphic. That is, there is an arrangement \ (P \), change the number of one tree \ (I \) to \ (p_i \), so that this tree is exactly the same as the other tree. What can tree hashes be used for Sometimes we need to judge whether some trees are isomorphic. At this ti ...

Algorithmic thought Definition of bipartite graph: if all vertices of a graph can be divided into X X X and Y Y Y two sets, and for all edges, the two points of the edge do not belo ...

summary There is A sequence A composed of N Boolean values, which gives some restrictive relations, such as A[x] AND A[y]=0, A[x] OR A[y] OR A[z]=1. It is necessary to determine the value of A[0 * n − 1] so that it meets all restrictive relations. This is called the SAT problem (it has been determined that the SAT problem that is not 2-S ...

subject Give you a two-dimensional grid composed of '1' (land) and '0' (water). Please calculate the number of islands in the grid. Islands are always surrounded by water, and each island can only be formed by adjacent land connections in the horizontal and / or vertical direction. In addition, you can assume that all four sides of the mesh ...

Introduction Knowledge points involved Thinking, multiplicative inverse, combinatorial mathematics, topological sorting, DP, bipartite graph, maximum weight matching, plane geometry Link: Nanjing 2019 regional competition [Cloned] subject A Give a positive integer n and find the smallest integer k to make the set ...

1, Interval dp As the name suggests, interval dp is the problem of solving the optimal value on the interval. The main idea is to solve the inter cell first, and then use the optimal solution combination between cells to obtain the optimal solution of the maximum interval. If you don't say much, go straight to the example: Classic example: ...

preface There should be no cancer. People will go to cards \ (\ textsf{Dinic} \) and \ (\ textsf{ISAP} \). Maximum flow First, define what we want to do - find the maximum flow. Then use the most common analogy: the source point is the water delivery from the waterworks, and all the water output from the source point needs to flow into the sewa ...