Now the following problem is known and you are told that this problem can be solved by network flow, what should you do and how should you model the network flow?
Some prerequisites:
Apparently it can be foundNever go sideways to the left.，But may go vertical up the side(as shown below)
Then the diagram actually looks like this: ask from\(s\) until (a time)\(t\) Minimum cost of the
Without that\(m\) Article restrictions, we can just run the shortest circuit, plus these restrictions, found that it is actually a network flow model, consider how to build out the network flow model.
Modeling:
We fictionalize the following model to make it easier to understand - a very canonical model:Pairwise diagrams!(Learn exactly what a dyadic diagram is on your own)
Note: The side with no direction is that it's not clear what to build at this point, so I'll consider that later.
The weight of each red edge (an edge on the network flow) is the weight of the black edge (the actual graph) it crosses
(Like a *.) Now the shortest time it actually takes to get from s to t is actually s until (a time) t of the red connecting edges form the minimal cut of the graph.
Why? Let's deduct two separate points to prove it:
As in the above figure, if we disregard the horizontal red edge first, according to the knowledge of the minimum cut, we know that the path in the\((s,x) and (x,t)\) One and only one of them must be cut in the same way as in the\((s,y) and (y, t)\) One and only one of them must be cut, (one must be cut to satisfy the fact that no augmentation path can go from s to t);
Why can only one of each be cut off?
- If we make sure we need to cut\((x,y)\) This side will only be cut again.\((s,y),(x,t)\)Otherwise both the cut\((s,y),(s,x)\) or cut\((x,t),(y,t)\) Both would make it unnecessary to cut\((x,y)\), contradicting the need for reassurance.
- truncate\((y,x)\) Id;
- if neither cut nor cut at all\((x,y)\) I don't cut it either.\((y,x)\)：
- If it's guaranteed to need to be cut\((x,t)\)Then you'll need to cut it.\((y,t)\) When we don't have to cut the other side, it doesn't need to be explained. Then if we cut\((s,y)\) What about, so that there is still the augmentation path s->x->y->t, at this point because we neither cut the\((x,y)\) I don't cut it either.\((y,t)\)That's why it has to be cut.\((s,x)\)At this point, it will be found that\((s,x) and (x,y)\) It's all cut out, then.\((x,t)\) is no need to cut, paradoxically!
- uncut\((x,t)\) words, ditto.
Compare this with the actual diagram and find the same, if you take the side 1->2, you must not take the side 4->5, and if you take 2->3 you must not take 5->6;
If it goes 2->5, then it either goes 1->2->5->6 or 4->5->2->3.
So it's actually possible to findThe minimum cut is the shortest circuit in the original figure。
Having solved the above problem, then now we just need to solve again the\(m\) The two problems are the constraints and the red edges in the * diagram that have no direction (the edges of the leftmost and rightmost points).
How to solve\(m\) A limit?
Still, two points are deducted, (only the model points are deducted), and if the topic restricts the simultaneous travel of s->x and y->t (x and y are not necessarily adjacent), it is necessary to add another point of size\(c\) The spend. (For the moment, treat this as if there were no dotted edges)
Then it is equivalent that we need to consider how to make an additional cut of s->x and y->t with a cost of\(c\) We then build an edge from y to x at a cost of\(c\) The edges of the picture are solved. (That's the dashed edge in the diagram).
Obviously after cutting s->x and y->t, there is an augmentation path s->y->x->t, so y->x must be cut again (it has been proved above that at this point there will be no further cuts of x->t and s->y). ok.
The treatment of the leftmost and rightmost points
Now take that rightmost part of the edge and obviously it can be connected like this:
It can be noticed that between sides 1 and 2 (obviously only one of these two sides can be taken) if we take 2, nothing happens; but if we take the side 1, then we must take the side 3. Consider how to solve this on a network stream.
It means that when you need to choose between a and b to cut the edge of a, you have to cut the edge of e as well.
In fact, the d weight is attached to 0, c is attached to inf, and then e is connected to the left one from the right one, which ensures that d is not cut c. At this time, if a is cut, e needs to be cut in order to make the widening of the road c-e-b is no longer widening.
Below: