[network flow] maximum flow: algorithm template, bipartite graph matching
Algorithm template
Time complexity of Ek algorithm: O(nm2)O(nm^2)O(nm2)
Give a flow network and maintain the residual network.
while(){
①Find Zengguang road in the current residual network(bfs):f'
②Update residual network:Put the current residual network Gf Residual network updated to new stream G(f+f')
}
① Simple traversal, bfsbfsbfs can b ...
Posted by caraldur on Wed, 25 May 2022 10:15:55 +0300
[immortal title] [LCA] Luogu P1852 jump checkers
Link
That's a good question,
subject
solution
From "only one chess piece can be skipped at a time", an important property of this question is obtained:
There are at most three jumping methods for these three chess pieces at a certain time: the middle piece jumps left and right, or the piece closer to the middle piece jumps to the m ...
Posted by phpScott on Tue, 24 May 2022 02:25:07 +0300
[SPFA] [bisection] set up telephone line
LinkLinkLink
luogu P1948luogu\ P1948luogu P1948
DescriptionDescriptionDescription
Farmer John plans to lead the telephone line to his farm, but the telecom company does not intend to provide him with free services. Therefore, FJ must pay a certain fee to the telecom company.
Around the farm of FJ, there are n (1 < = n < = 1000) abandoned ...
Posted by duclet on Mon, 23 May 2022 10:52:56 +0300
Introduction to graph theory, some basic concepts of graph theory and practical combat
Basic concepts
A graph is a set of N vertices and M edges. Graphs are divided into directed graphs and undirected graphs. If a direction is specified for each edge of a graph, the resulting graph is called a directed graph, and other edges are also called directed edges. In a directed graph, the edge associated with a point can be divided in ...
Posted by shure2 on Sun, 22 May 2022 21:16:43 +0300
Analysis of typical examples of acm network flow and cost flow
introduction
The general difficulty of the problems of network flow and cost flow type lies in drawing. This paper mainly summarizes the various difficulties encountered by the author in the process of doing exercises and explains them in the form of examples.
On the relevant principles of network flow and cost flow, many blogs written in gre ...
Posted by newzub on Sun, 22 May 2022 16:31:05 +0300
[problem solution] P1073 [NOIP2009 improvement group] optimal trade (graph theory, shortest path, SPFA)
[problem solution] P1073 [NOIP2009 improvement group] optimal trade
This question is wonderful!
Although this is only a green question, it still stuck me for a long time. The main reason is that there are two ideas in this question, which I totally didn't think of. I'm too hungry
Write down ideas to record this wonderful topic.
Title Link
[NOI ...
Posted by ALEXKENT18 on Sun, 22 May 2022 03:27:34 +0300
ACwing 257 - detaining criminals (dichotomous answer + dichotomous coloring)
There are two prisons in S City, holding a total of N criminals, numbered 1~N respectively.
Naturally, the relationship between them is also extremely disharmonious.
Many criminals have even accumulated grievances for a long time. If the objective conditions are met, conflicts may break out at any time.
We use "resentment value" (a po ...
Posted by hame22 on Fri, 20 May 2022 15:31:44 +0300
2020-09-03 / 04 test question solution
2020-09-03 test questions
Hobson's Trains
Title portal
General idea of the topic
Give a graph to ensure that each point has only one edge. For each point, add 1 to all the point answers on the path of \ (k \) step, and ask the answer of each last point.
\(n\le 5\times 10^5\)
thinking
It was sb time for the exam and I didn't figure out how to do ...
Posted by frosero on Wed, 18 May 2022 15:53:14 +0300
Data Structure Chapter 6 Graph Study Notes
content
1. Figure
6.1 Definition of graph
6.2 Basic terminology of graphs
6.3 Graph storage structure
6.3.1 Lead matrix
6.3.2 Adjacency List
6.4 Traversal of graphs
6.4.1 Depth-First Search (DFS)
6.4.2 Breadth-First Search (BFS)
6.5 Applications of graphs
6.5.1 Minimum Spanning Tree
6.5.2 Shortest path
6.5.3 Topolog ...
Posted by Ramtree on Wed, 18 May 2022 01:04:31 +0300
"War epidemic Cup" online invitational tournament -- solution to game 5
"War epidemic Cup" online invitational tournament -- solution to game 5
Topic details - 1 where is the source of infection (pintia.cn)
Through a recent nucleic acid test, the epidemic prevention and control team detected several positive persons. By retrieving the trip code data, the prevention and control team obtained the places w ...
Posted by torvald_helmer on Sat, 14 May 2022 00:40:22 +0300