c++ programing problem28 Max Flow Time Limit: 2 seconds Problem Description For

Question

c++ programing problem28

Max Flow

Time Limit: 2 seconds

Problem Description

For a graph G = ( V, E ), we can regard the edges on the graph as a water pipe, and each water pipe has its own capacity

Now we select a point as the source and select another point as the target. The source can flow infinitely

the end point can accept the water flow infinitely, and the inflow and outflow of other points must be equal, meaning that there is a flow of water coming in,

There must be a limit to how much water flows out and the point itself does not have a capacity, but the flow of water through the water pipe must not exceed the upper limit of the capacity of the water pipe.

What is the maximum flow that a given s-t combination can allow?

Input File Format

There will be a positive integer N at the beginning, which means that there will be next N input data.

The first line of each input data has two positive integers n and m, representing a total of n points and m edges on the graph. Each point is numbered 0~n-1.

0 is source and n-1 is sink.

The next m rows each have three positive integers u, v, and c, representing a directed edge that connects from u to v and capacity is c.

1 ? n ? 500, 1 ? m ? 5000, c is 32-bit unsigned integer.

Output Format

Each line outputs max flow and ends with a newline for each input data

Explanation / Answer

Solution:- I'm going to paste the code that is running on my PC just fine, However, do comment if you face any difficulty,

==================CODE BEGINS===================

#include <cstdio>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <iostream>

#define MAX_NODES 500 // the maximum number of nodes in the graph
#define INF 2147483646 // represents infinity
#define UNINITIALIZED -1 // value for node with no parent

using namespace std;

// represents the capacities of the edges
int capacities[MAX_NODES][MAX_NODES];
// shows how much flow has passed through an edge
int flowPassed[MAX_NODES][MAX_NODES];
// represents the graph. The graph must contain the negative edges too!
vector<int> graph[MAX_NODES];
// shows the parents of the nodes of the path built by the BFS
int parentsList[MAX_NODES];
// shows the maximum flow to a node in the path built by the BFS
int currentPathCapacity[MAX_NODES];  

int bfs(int startNode, int endNode)
{
memset(parentsList, UNINITIALIZED, sizeof(parentsList));
memset(currentPathCapacity, 0, sizeof(currentPathCapacity));

queue<int> q;
q.push(startNode);

parentsList[startNode]=-2;
currentPathCapacity[startNode]=INF;

while(!q.empty())
{
int currentNode = q.front(); q.pop();

for(int i=0; i<graph[currentNode].size(); i++)
{
int to = graph[currentNode][i];
if(parentsList[to] == UNINITIALIZED)
{
if(capacities[currentNode][to] - flowPassed[currentNode][to] > 0)
{
// we update the parent of the future node to be the current node
parentsList[to] = currentNode;

// we check which is the minimum residual edge capacity so far
currentPathCapacity[to] = min(currentPathCapacity[currentNode],
capacities[currentNode][to] - flowPassed[currentNode][to]);
  
// if we have reached the end node the bfs should terminate
if(to == endNode) return currentPathCapacity[endNode];

// we add our future node to the queue
q.push(to);
}
}
}
}

return 0;
}

int edmondsKarp(int startNode, int endNode)
{
int maxFlow=0;

while(true)
{
// we find an augmented path and the maximum flow corresponding to it
int flow=bfs(startNode, endNode);
  
// if we can't find anymore paths the flow will be 0
if(flow==0)
{
break;
}

maxFlow +=flow;
int currentNode=endNode;
  
// we update the passed flow matrix
while(currentNode != startNode)
{
int previousNode = parentsList[currentNode];
flowPassed[previousNode][currentNode] += flow;
flowPassed[currentNode][previousNode] -= flow;

currentNode=previousNode;
}
}

return maxFlow;
}

int main()
{
int nodesCount, edgesCount, tc;
cin>>tc;
while(tc--) {
cin>>nodesCount>>edgesCount;

int source = 0, sink = nodesCount-1;

for(int edge=0; edge<edgesCount; edge++)
{
int from, to, capacity;
cin>>from>>to>>capacity;

capacities[from][to]=capacity;
graph[from].push_back(to);

//adding the negative edge
graph[to].push_back(from);
}

int maxFlow = edmondsKarp(source, sink);

cout<<maxFlow<<endl;
for (int i = 0; i < 500; ++i)
{
graph[i].clear();
}
}

return 0;
}

===============CODE ENDS==============

Note:- Do comment if you need any screenshot, Then i'll update it. Also, Please upvote.

Thanks!

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.