POJ1273-Drainage DitchesAnalysis:This problem requires that we find the maximum flow over a given network,explicitly.In Graph Theory,this is catagorized as the
Maximum-Flow problem.The concept here is that,given a network with nodes,which are regarded as dispatchers,we specify a value for each path(namely,edges of the graph which connect two different nodes,obviously),as the
capacity of this path.Among all the nodes,one of them is supposed to be the
source of the network,where all the flows begin,and another one of them the
sink,where all the flows end.Our aim then,is to work out the maximum flow we can get through this network,in respect of the following conditons:
First,for each node except for the source and sink,the flow into and out of it must be equal;
Second,all the flow along the pathes cannot be over the capacity of them,respectively.
As a result,we have the following rules of the
Maximum-Flow problem,where f(u,v) denotes the flow from node u to v,and c(u,v) denotes the capacity of the path between them.Note that the path is a one-way street(directional):
1.f(u,v)<=c(u,v),this is called the capacity constraints;
2.f(u,v)=-f(v,u),this is called the skew symmetry;
3.for all nodes except the source and sink,the sum of f(u,v)=0,this is called the flow conservation.
Note that we only allow one of f(u,v) and f(v,u) to be positive,for we can obviously see that transmitting 5 units of goods from u to v and 2 units of goods from v to u simultaneously doesn't seem to be so practical.
There are several theorems that we can apply when attempting to solve this sort of problems.One of them is the Augmenting Path Theorem,which states that the flow of a network will not be maximum until there does not exist an
augmenting path anymore.This is actually the foundation of several algorithms used to calculate the Max-Flow problem.One of them is called the
Edmonds-Karp Algorithm.The whole idea of this algorithm derives from the theorem above,and actually is an improvement based on the Ford-Fulkerson method.To make it simple,all we need to do is to constantly look for an
augmenting path for the
residual network until there does not exist an
augmenting path anymore.According to the theorem above,this fact implies that we have found the maximum flow for a certain network.Oh yes,the residual network!Well,this is quite simple.Assuming that we now have a flow value for some nodes,and its capacity as well.The margin between those two is defined as the residual value for the node.A network with all nodes carrying its residual value is called the residual network.
The algorithm can be implemented like this:
First we initialize the flow value for each path f[i][j]=0(or actually anything that satisfies the constraints above);
Then we gradually increase the flow value by constantly finding the minimum residual value for all the paths each time,using the
Breadth-First-Search method.More precisely,starting from the
source node,we push every new node we find(here new means that this node has not been encountered before,and that it has a path connected to it from the current node we're dealing with) into a
FIFO queue.If the path between the current and the new node has a capacity higher than the current flow value assigned to it,then it can be added to the current
augmenting path we're trying to establish.That being true,we update the
residual value of the new node and go on searching.
Finally,we will deal with the residual value of the
sink node,which is supposed to be discovered at the very end of the searching above.If the residual value for it is zero,as we initialize it,it would mean that we failed to find an augmenting path of the residual network this time.Obviously,that implies the end of the process.Otherwise,we update each path's flow value by increasing(or decreasing if it is an edge going backward) by the
minimum residual value we have found this time(actually the res[sink]),and add that value to the result maxflow as well.
Now we're done!As long as the process above ends,we can get the maximum flow of the whole network we want!In fact,this idea is quite natural if we take a look at it the simplest way.All we have done has been nothing but experimenting.Imagine that we now have a ball which we want to throw from one hole to another through some tunnel whose structure we do not acknowledge.What will we do?We will increase the diameter of the ball bit by bit,and see if it can reach the other hole fluently.Assuming the margin can be small enough,we will ultimately find the maximum diameter for the ball.And that is when the moment comes as we cannot put the ball into the hole,or the ball gets stuck somewhere in the middle,thus never shows up again.This is actually a lousy example,since the ball apparently cannot be divided into streams and transmitted through several tunnels at the same time.However,this is easy enough to understand.
Ok,now we're capable enough to solve this problem.This is a basic problem for maximum flow.Actually,it is explicitly a maximum flow problem.The problem can be stated as,find the maximum flow from node 1 to node n,given the capacity of the m paths in the network.By implementing the algorithms above,this problem is in control.
Code:
1 #include<cstdio>
2 #include<cstring>
3 #define MAXSIZE 201
4 #define INF 100000001
5 using namespace std;
6 int network[MAXSIZE][MAXSIZE];//used to record the information of each node,network[i][j] denotes
7 //the capability of flow from i to j
8 int maxflow;//used to denote the final result
9 struct Lineup
10 {
11 int q[MAXSIZE];
12 int head,tail;
13 }Myqueue;//simulate a FIFO queue using array
14 int flow[MAXSIZE][MAXSIZE],residual[MAXSIZE];//flow used to record the information of each single-path
15 //while residual is the residual flow
16 int pre[MAXSIZE];//used to store the previous node while BFS search
17 void Edmonds_Karp(int source,int sink,int n)
18 {
19 maxflow=0;//Initialize the result maxflow
20 memset(flow,0,sizeof(flow));//Initialize the flow value for each path
21 while(1)
22 {
23 Myqueue.head=0;Myqueue.tail=1;//Initialize the queue
24 memset(residual,0,sizeof(residual));//initialize the residual flow for each path
25 residual[source]=INF;
26 Myqueue.q[Myqueue.head]=source;
27 while(Myqueue.head<Myqueue.tail)
28 {
29 int u=Myqueue.q[Myqueue.head++];
30 for(int v=1;v<=n;v++)
31 {
32 if(v==u) continue;
33 if(!residual[v] && network[u][v]>flow[u][v])//encounter a new node v
34 {
35 pre[v]=u;Myqueue.q[Myqueue.tail++]=v;//mark its previous node and push it into the queue
36 residual[v]=(residual[u]<network[u][v]-flow[u][v]) ? residual[u] : network[u][v]-flow[u][v];
37 //update the minimum residual value of the path from source to v
38 }
39 }
40 }//Augmenting
41 if(residual[sink]==0) break;//if there's no more lower residual value for sink,then break
42 for(int u=sink;u!=source;u=pre[u])
43 {
44 flow[pre[u]][u]+=residual[sink];
45 flow[u][pre[u]]-=residual[sink];
46 }//update the flow value for each path forward and backward
47 maxflow+=residual[sink];//update the maxflow value
48 }
49 }
50
51 int main()
52 {
53 int ditches,intersection;
54 int s,e,c;
55 while(scanf("%d %d",&ditches,&intersection)==2)
56 {
57 memset(network,0,sizeof(network));
58 for(int i=0;i<ditches;i++)
59 {
60 scanf("%d %d %d",&s,&e,&c);
61 network[s][e]+=c;//Attention!Input can include ditches that have appeared before
62 }
63 Edmonds_Karp(1,intersection,intersection);
64 printf("%d\n",maxflow);
65 }
66 return 0;
67 }
68
Last but not least,the time complexity of the EK algorithm is supposed to be O(VE
2 ).