- Introduction
- Prequisites
- Compilation
- Execution
- Top-Down Analysis
The program baseballEliminations.cpp is used to determine which teams have been mathematically eliminated from the division in a sports league when standings are given at some point during the season. When provided with the input, this program, for each team creates a flow network and applies the Edmonds–Karp version of Ford-Fulkerson algorithm to find the max flow and hence determine if the team is eliminated or not.
- For a full description of the problem, visit here.
- For a full description of the Edmonds-Karp algorithm, visit here.
- First a c++ compiler like, g++ (MinGW.org GCC Build-20200227-1) 9.2.0, should be installed.
- Then iostream, fstream, sstream, climits, string, vector, stack, queue and algorithm header files should be available.
- The input format is the number of teams in the division n followed by one line for each team. Each line contains the team name (with no internal whitespace characters), the number of wins, the number of losses, the number of remaining games, and the number of remaining games against each team in the division.
- In windows,
g++ -o baseballElimination.exe baseballElimination.cppcommand in command prompt will compile an create an executable. - In linux,
g++ baseballElimination.cppin terminal will create the object.
- In windows,
baseballElimination.execommand in command prompt will execute the program. Just enter the input file path. - In linux,
./a.outin terminal will execute the program. Again enter the input file path.
- First the input file is used to create a division. Here division is a class which stores all the data in their right data type.
- Then after creating an object of divison we use it to create a flow network which is a class for graph. There we use the Ford-Fulkerson algorithm to determine if the team is eliminated or not.
- Avanish Kumar Singh