Maxflow for baseball elimination game

Question

I have a problem similar to the baseball elimination. Given some teams, the number of wins they have and the number of games they have left between each other I have to find for which team it is still possible to win. I am using the maxFlow algorithm to solve it. First I build a graph without the team I am currently checking and check if the graph is saturated a the source, by checking if the maxFlow is less or equal to the maximum capacity of the source. Is this implementation correct, and how can I improve it?

#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <stdio.h>

using namespace std;

#define MAX 100000
#define pii pair <int,int>
#define pip pair <pii,int>
vector<int> wins;
vector<vector<int> > games;
vector<int> remaining;
int maxWins = 0 ;


bool BFS(vector<vector<int> > residualCapacity, int parent[], int source, int sink)
{
    //BFS for maxFlow
    int n = residualCapacity.size();
    bool visited[n];//= {};
    fill_n(visited, n, false);
    queue<int> Q;
    Q.push(source);
    visited[source]=true;
    bool foundPath=false;
    while(!Q.empty())
    {
        int current = Q.front();
        Q.pop();
        for( int v=0; v< n; v++)
        {
            int cost = residualCapacity[current][v];
            if(!visited[v] && cost>0)
            {
                parent[v]=current;
                visited[v]=true;
                Q.push(v);
                if(v==sink)
                {
                    foundPath=true;
                    break;
                }
            }
        }
    }
    return foundPath;
}

int maxFlow(vector<pip> capacity, int source, int sink, int n)
{
    int x = capacity.size();
    vector<vector<int> > residualCapacity (n, (vector<int> (n,0) ));
    for (int i = 0; i < x; i++)
    {
        int from = capacity[i].first.first;
        int to = capacity[i].first.second;
        int cap = capacity[i].second;
        residualCapacity[from][to] += cap;
    }


    int parent[n];
    //list<list<int> > augmentedPaths;
    int maxFlow=0;
    while(BFS(residualCapacity, parent, source, sink))
    {
        //list<int> augmentedPath;
        int flow = MAX;
        int v = sink;

        while(v!=source)
        {
            //augmentedPath.push_back(v);
            int u = parent[v];
            if(flow > residualCapacity[u][v])
                flow = residualCapacity[u][v];
            v=u;
        }
        //augmentedPath.push_back(source);
        //augmentedPath.reverse();
        //augmentedPaths.push_back(augmentedPath);
        maxFlow += flow;

        v=sink;
        while(v!=source)
        {
            int u = parent[v];
            residualCapacity[u][v] -= flow;
            //residualCapacity[v][u] -= flow;
            v=u;
        }
    }
    return maxFlow;
}

//create graph without the node we are checking if is eliminated
bool buildGraphFor(int id, int n)
{
    int maximumFlow = 0;
    int source = n;
    int sink = n+1;
    int gameNode = n+2;
    int currentMaxWins = wins[id] + remaining[id]; //


    vector<pip> edges;
    for (int i = 0; i < n; i++)
    {
        if (i == id || wins[i] + remaining[i] < maxWins)
        {
            continue;
        }

        for (int j = 0; j < i; j++)
        {
            if (j == id || games[i][j] == 0 || wins[j] + remaining[j] < maxWins)
            {
                continue;
            }
            maximumFlow +=games[i][j];

            edges.push_back( pip(pii(source,gameNode),games[i][j]));
            edges.push_back( pip(pii(gameNode,i),MAX) );
            edges.push_back( pip(pii(gameNode,j),MAX) );
            gameNode++;
        }
        int value = currentMaxWins - wins[i];
        edges.push_back( pip(pii(i,sink),value) );
    }


    int currentCap = maxFlow(edges, source, sink, gameNode);
    return (maximumFlow<=currentCap);
}

int main()
{
    int n, m, w, cases, a, b;
    cin>>cases;
    for(int c=1; c<=cases; c++)
    {
        cin>>n>>m;
        wins.resize(n);
        games.assign(n,(vector<int>(n, 0)));
        remaining.assign(n,0);
        bool teams[n];
        for(int t=0; t<n; t++)
        {
            cin>>w;
            wins[t]=w;
        }
        for(int p=0; p<m; p++)
        {
            cin>>a>>b;
            games[a-1][b-1] += 1;
            games[b-1][a-1] += 1;
            remaining[a-1]+=1;
            remaining[b-1]+=1;
        }

        for(int s=0; s<n; s++)
        {
            teams[s] = buildGraphFor(s, n);
        }
        cout<<"Case #"<<c<<": ";
        for(int o=0; o<n; o++)
        {
            if(teams[o])
                cout<<"yes ";
            else
                cout<<"no ";
        }
        cout<<endl;


    }
    return 0;
}

Answer 1

Simple Code Review

Headers

There is a C++ version of this header file. It puts all the functions in the std:: namespace.

#include <stdio.h>
// Prefer
#include <cstdio>

Using namespace Std

Prefer never to use this:

using namespace std;

See: Why is “using namespace std” in C++ considered bad practice?. Basically it is a bad habit that you should break. There is a reason the standard namespace is so short std:: and not standard::; it is so that prefixing items from the standard namespace is not overly taxing.

Macros

There is no need to use macros for this type of thing.

#define MAX 100000
#define pii pair <int,int>
#define pip pair <pii,int>

Most macro usages can be replaced by C++ language level features. Save macros for what they are truly useful for (platform dependent code).

constexpr int max = 100000;
using pii = std::pair<int,int>; // alternatively use typedef
using pip = std::pair<pii,int>;

Overly old style

Adding the extra space between > characters in a template has been fixed 5 years ago.

vector<vector<int> > games;
// Be consistent and dont add the space
vector<vector<int>>  games;

Global mutable state

All the above variables are at file level scope (commonly referred to as global variables). This is BAD design. global mutable state makes the program hard to test and validate. You should "probably" wrap these in a class object with the following functions being members of that class. Then declare an instance of the object inside main.

Parameter passing

Passing an array and a size is notoriously dangerous.

bool BFS(vector<vector<int> > residualCapacity, int parent[], int source, int sink)
                                                ^^^^^^^^^^^^^^^^^^^^^^^^^^

There is no way for the function to know that n is correct for the parent. Thus in C++ this is rarely done. You normally pass a reference to a container or if you want to abstract the container you pass iterators.

Passing containers by value is epensive as you need to make a copy of the container.

bool BFS(vector<vector<int> > residualCapacity, int parent[], int source, int sink)
         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

SO normally you pass it by const reference (so you can mutate the original).

Variable Sized arrays (VSA)

Thus is a non standard extension. As such you should prefer not to use it. Prefer vector instead.

    int n = residualCapacity.size();
    bool visited[n];//= {};

Self documenting code

Q is a terrible name. The standard naming convention for C++ is that an initial lowercase defines an object and initial uppercase defines a user defined type. SO it breaks standard naming conventions. Also a name this short has no meaning.

    queue<int> Q;

Path Tracing

The following looks like a best path problem.

    while(!Q.empty())
    {
        int current = Q.front();
        Q.pop();
        for( int v=0; v< n; v++)
        {
            int cost = residualCapacity[current][v];
            if(!visited[v] && cost>0)
            {
                parent[v]=current;
                visited[v]=true;
                Q.push(v);
                if(v==sink)
                {
                    foundPath=true;
                    break;
                }
            }
        }
    }

You may want to look up a better algorithm (Like Dijkstra's algorithm).

For Loops.

There are three ways to loop over a container.

// The original way inherited from C
std::size_t size = cont.size();
for(std::size_t loop = 0; loop < size; ++loop)
{
    auto const& item = cont[loop];
    // STUFF
}

// using iterators
for(auto loop = cont.begin(); loop != cont.end(); ++loop)
{
    auto const& item = *loop;
    // STUFF
}

// Using range based for
for(auto const& item : cont)
{
    // STUFF
}

Always use '{...}' around sub blocks

            if(flow > residualCapacity[u][v])
                flow = residualCapacity[u][v];

Prefer to put braces around sub blocks. There is still old nasty C macros hiding out there that will break your code if you use them incorrectly. Just play safe and add the braces.

            if(flow > residualCapacity[u][v]) {
                flow = residualCapacity[u][v];
            }

In this case though you could have used std::min().

Remove commented out old code

        //list<int> augmentedPath;
            //augmentedPath.push_back(v);
        //augmentedPath.push_back(source);
        //augmentedPath.reverse();
        //augmentedPaths.push_back(augmentedPath);

Comments

Normally I don't recommend comments. As the code should explain what it is doing. But your code is sufficiently complicated that I don't understand what iit is ding at first glance. So a description of what is trying to achieve would be nice (name the algorithm if you can). Note: Don't describe WHAT the code is doing describe WHY or the OBJECTIVES.