graph theory , It's actually a branch of Mathematics , It takes pictures as its research object . The most basic graph theory should be the famous Seven Bridge problem of gunnysburg , That is a classic one stroke problem .
What we often see in competitions is Shortest path algorithm Minimum spanning tree algorithm A topological sort wait .
In this article, we won't talk about graph theory algorithms that everyone knows badly , Talk about some practical ( It's no use ) Graph theory tips .
Chain forward star map
There are two basic ways to store graphs , Use two-dimensional arrays and \(vector\) , But both of these methods have shortcomings .
Using two-dimensional array query speed is very fast , But the spatial complexity is \(O(n^2)\) Of , General topics are unacceptable .
Use \(vector\) It can reduce the space complexity , But the time is more uncertain .
So there is a magical way to save pictures , Chained forward star of linked list thought .
We usually use the following array to complete
$Codes$
int w[i]// The first i The weight of the edge
int to[i]// The first i The end of the edge
int nxt[i]// The number of the next side , Not recommended next, Can hang
int head[i]// With i Is the first edge of the starting point
int tot// The number of the side
When adding a new edge, we do the following
$Codes$
void add(int x,int y,int z){
tot++;// The number of the new side
to[tot]=y;// Information on a new side
w[tot]=z;
nxt[tot]=head[x];
head[x]=tot;// Update to x Is the first edge of the starting point
}
// This is a one-way edge , Two way side again
You can enumerate all in the following way xx An edge that is the starting point .
$Codes$
for(int i=head[x];i;i=nxt[i]){// i It is the number of this side
//to[i] Nod for what can be reached
//w[i] Is the weight of this edge
}
The general idea is to take everything as \(x\) The edge as the starting point is stored in the form of a linked list , When enumerating, traverse the linked list , Until the number of the side is \(0\) ( by \(0\) It means that there are no other edges )
In this way, we can meet the needs of traversing and enumerating the next point from a certain point .
Forward star linked list is wildly used in various graph theory topics , Basically, a graph theory can be used , It belongs to a very basic graph theory skill .
What needs to be noticed is the problem of two-way edges , The array of chained forward stars requires twice the number of open sides , Otherwise \(RE\) .
Reverse side building
For a directed graph , In some problems, we need to reverse edge building to complete the operation
For example, ask others \(n\) It's one o'clock \(k\) The shortest path of the point .
Wouldn't it be good to run for the shortest circuit at each point ？
In fact, we only need to run the shortest circuit once , Just reverse the side .
In the case of reverse mapping \(k\) The shortest path from a point to each point is from that point to \(k\) The shortest path of the point .
Example P1629 The postman delivers the mail
It's not just the shortest path , You can also use reverse edge building to complete the traversal problem
Example P3916 Graph traversal
Whether it is necessary to reverse edge construction , Judge according to the meaning of the question .
Reverse edge building can also be used to judge whether an edge is on the shortest path .
For a directed graph , We from 11 Run through the shortest path in the positive direction \(dis[]\) , from \(n\) Run through the reverse shortest circuit at the No \(dis1[]\)
If \(dis[x]+w(x,y)+dis1[y]=dis[n]\) Then we can come to the conclusion that , This side is \(1\) To \(n\) On the shortest circuit of .
Of course, if it is an undirected graph, just run directly .
Virtual points and edges
Connecting virtual points with edges is a very effective way to optimize the complexity of edge building
We may encounter such a problem , I'll give you some , What is the nearest distance between other points and these given points .
We can do for each point \(Spfa\), But it seems that this is not very easy to operate .
We can give a point by ourselves , Then connect a unidirectional edge to each marked point , This only needs to be done once \(Spfa\) That's all right. .
for instance , Orange is the marking point , The number is the nearest distance .
Example P3393 Escape Zombie Island
But it seems that this direct search can also .
If for two point sets \(A\) and \(B\), You need to \(A\) Every point in \(B\) An edge is built at every point in the , If you do it directly , The complexity is obviously \(O(n^2)\) Of , Is there a faster way ？
We can build a virtual dot \(P\) , Then on \(A\) Every point in the \(P\) Connect a one-way side , Then on \(P\) towards \(B\) A one-way edge is built for each point in , It just needs \(O(2n)\) The complexity can be completed .
So let me draw a picture of that .
( Before optimization )
( After optimization )
Example P1983 Station classification
Virtual dots and edges are just operations that sound very tall , But it's actually very simple .
For the case with edge right , The edge weight of the edge connected by the imaginary point needs attention ( It's usually \(0\) )
The line tree optimizes the edge construction
Speaking of optimizing edge construction , We must introduce the optimization and edge building of segment tree .
This is also a skill that sounds very tall but in fact is not very difficult .
Give you a point \(X\) , Let you connect an edge with every point in a point set . There seems to be no good way , Only one company can be obedient
What if this point set is continuous ？ We can use the segment tree to optimize the edge construction .
We know that the segment tree is of this structure
We know , The points of the line segment tree can represent an interval , So how do we apply this property ？
First , We need to build a one-way edge for each father and his son of the segment tree , The effect is as follows
What's the use ？ Because the set of points we require is a continuous interval , The nodes of the segment tree can represent a certain interval , We can find the corresponding interval in the segment tree , Then create an edge to the point on the line segment tree , You can speed up the speed of edge construction .
For example, we want to \([1,8]\) All points in the build side , We just need to put \(X\) And line segment tree \([1,8]\) That point can be connected with a one-way edge .
\([2,6]\) Example
Our edge weight on the segment tree is generally \(0\) , The edge right is directly assigned to \(X\) Connect to the edge of the line segment tree
The code for building and searching trees is similar to that of ordinary segment trees . It should be noted that the number of nodes on the segment tree should not be repeated with the existing points , Just connect the last node directly to this point .
$Codes$
void build(int &p,int l,int r){
if(l==r){
p=l;
return ;
}
p=++cnt;// Number of points
int mid=l+r>>1;
build(lc[p],l,mid);build(rc[p],mid+1,r);
add(lc[p],p,0);add(rc[p],p,0);
}
void update(int p,int l,int r,int x,int L,int R,int z){
if(L<=l && r<=R){
add(x,p,z);
return ;
}
int mid=l+r>>1;
if(L<=mid){
update(lc[p],l,mid,x,L,R,z);
}
if(R>mid) {
update(rc[p],mid+1,r,x,L,R,z);
}
}
Example CF786B Legacy
This problem also involves the case that the interval connects to a certain point , Let's build another line segment tree and build an opposite side on the tree
Disassemble points and compose pictures
Sometimes we can't use a point to represent a point （ Fog ）
Well, I didn't mean that . I mean to use several points to express the different situations of a point .
A question with random muzzle
A picture , On each side there are \(k\) Weight , The first \(i\) The cost of the first walk is \(i\%k+1\) Weight , Find the single source shortest path of a point . \(( k\) Very small \()\)
It seems to run directly \(dij\) and \(spfa\) It is not right , Counter examples can be cited .
have access to \(dfs\) , use \(dis[i][j]\) To \(i\) It's a little bit off \(m\) Step and \(m\%k+1=j\) The shortest solution , But it's too slow .
We can use the idea of disassembly , For a point \(i\) , Disassemble it into \(i , i+n , i+2*n , ...\) In this way \(k\) A little bit , As the step modulus to this point \(k\) Alternative points for different situations .
Then when we connect the edges, we assign weights to different situations to a certain situation , About the following ？
// We need to x To y Connect three sides w1 w2 w3
add(x,y+n,w1);
add(x+n,y+2*n,w2);
add(x+2*n,y,w3);
Here's a picture
Then run the shortest path on the obtained graph , The answer is to enumerate the situation to the end .
Similar examples P4568 Flight path
Graph theory modeling
Seems to be …… Some knapsack problems can be solved by the shortest path , It's just not necessary .
\(Let us AC it--\) Topic
\(Kodak\) Opened a small shop to earn extra money , Because the store is small , So only \(n\) Two kinds of goods with different prices are sold , But fortunately, wholesalers awesome , There is a good supply of goods , So there are unlimited pieces of each product .
For a variety of reasons , Sometimes customers have special requirements for the total purchase price , For example, computer scientist temas must pay a total price \(1024\) , The total price of bread to buy a gift for miss \(520\) perhaps \(1314\) , Or Zhang San, who is just looking for trouble, wants to buy \(0\) Yuan commodity
however \(Kodak\) There may not be \(1\) Yuan goods , So not all the prices can be found , So he needs a program to know whether a total price can be made up
It seems that you can solve this problem with a complete backpack , But the data range of this problem is not very friendly .
Number of goods \(N <= 1000\) \ commodity price \(a_i <= 20000\)
Number of customers \(M <= 300000\) \ Demand price \(b_i <= 40000000\)
If you pack completely , Complexity will explode .\(TAT\)
In fact, the problem is \(a_1*x_1+a_2*x_2+a_3*x_3+...?=k\) The problem of . We consider the \(“\) congruence \(+\) shortest path \(”\)
According to the meaning of the title , If \(k\) Meet the requirements , that \(a_m*k\) Must also meet the conditions . We can fill it up first \(a_m\) , Then subtract \(p\) individual \(a_m\) , With the rest of \(a_i\) Express \(p*a_m+k\%a_m\) Set as \(b\%a_m=i\) when , The smallest needed \(k×a_m+i\) by \(dis[i]\) , The rest can be updated with the shortest path idea ,
The process of running the shortest circuit is basically as follows
memset(dis,0x3f,sizeof(dis));
dis[0]=0;
q.push(0);
while(q.size()){
int x=q.top();
q.pop();
if(v[x]) continue;
v[x]=1;
for(int i=1;i<=n;i++){
int y=(x+a[i])%mod;
if(dis[y]>dis[x]+a[i]){
dis[y]=dis[x]+a[i];
q.push(y);
}
}
}
It may not be easy to understand , Combined with the sample, push it by hand
Another example
give \(n\) individual The length is \(m\) Of \(01\) strand , Let you decide on one with the same length \(01\) strand , The number of different digits in this string and the given string is the most .
A problem that seems to have nothing to do with graph theory , In fact, it can also be done as graph theory
We can build a \(2^m\) Graph , Each point is different from itself, and the number of digits is \(1\) The length of a line connecting the dots of is \(1\) The edge of , And then run \(bfs\), Getting the farthest point is what you want .
Search the code
while(h<=t){
int x=v[h];
for(int i=1;i<=m;i++){
int z=x^(1<<(i-1));
if(f[z]==0){
f[z]=1;
t++;
v[t]=z;
dis[z]=dis[x]+1;
}
}
h++;
}
This is a bit similar to the problem of connecting imaginary points and edges mentioned above .
What I said may be more delicious , Can draw pictures to understand .
The pit to pay attention to in graph theory
Briefly list a few small problems
\(1.\) First look at whether the eye is a directed graph or an undirected graph , The undirected graph array is doubled .
\(2.\) If the title does not state that there is no self ring and double edge , We need to pay attention to
\(3.\) Some traversal problems need to consider rings , Otherwise, there may be an endless cycle , You can use shrink points
\(4.\) If the edge weight in the topic is less than or equal to zero , Consider negative rings 、 The case of zero ring
\(5.\) The initial value should be given when running the shortest circuit .
\(6.\) About \(Spfa\) , You don't have to , After all, it's easy to get stuck .
