MOBIVINA SPOJ Mincut C++ Solution

Problem : MOBIVINA

Algorithm :

1. Add SOURCE and SINK nodes.
2. Set SOURCE-node edge capacity as per input array 1. (Directed edge SOURCE to node)
3. Set node-SINK edge capacity as per input array 2.(Directed edge node to SINK).
4. Set node-node edge capacity as per the last input matrix. (Add a directed edge for each "1" input).
5. Run Ford-Fulkerson algorithm.
6. Find mincut capacity (=ans).

Source :

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

using namespace std;
 
#define MAX 252

struct Edge{
    int from, to, flow, capacity;
    int other(int v){
        if(v==from)return to;
        else return from;
    }
    Edge(int f, int t, int c){
        from = f;
        to = t;
        capacity = c;
        flow =  0;
    }
    int residualCapacityTo(int v){
        if(from==v)return flow;
        else return capacity-flow;
    }

    void addResidualFlowTo(int v, int delta){
        if(from==v)flow -= delta;
        else flow+=delta;
    }
};


int N;
int Mi[MAX];
int Vi[MAX];
int reg[MAX][MAX];
int SOURCE = 0;
int SINK;

vector<vector<Edge> > g;

bool marked[MAX];
Edge* edgeTo[MAX];

bool hasAugmentingPath(){
    for(int i=0;i<=SINK;++i){
        marked[i] = 0;
        edgeTo[i] = NULL;
    }
    queue<int> q;
    q.push(SOURCE);
 bool found = false;
 marked[SOURCE] = true;
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(Edge &e:g[v]){
            int w = e.other(v);
   if(e.residualCapacityTo(w)>0 && marked[w]!=1){
                edgeTo[w] = &e;
                marked[w] = 1;
    if(w==SINK){found=true;break;}
    q.push(w);
            }
        }
  if(found)break;
    }
    return marked[SINK];
}

int fulkerson(){
    int mincutCap=0;
    int flow=0;

 int paths=0;
    while(hasAugmentingPath()){
  paths++;
        int bottle = 0x7fffffff;
        for(int v=SINK;v!=SOURCE;v=edgeTo[v]->other(v)){
   bottle = min(bottle, edgeTo[v]->residualCapacityTo(v));
        }
        for(int v=SINK;v!=SOURCE;v=edgeTo[v]->other(v)){
            edgeTo[v]->addResidualFlowTo(v, bottle);
        }
        flow+=bottle;
    }

    int cutCapacity=0;
 for(int i=SINK;i>=SOURCE;--i){
   if(marked[i]!=1)continue;
   for(int j=0;j<g[i].size();++j){
    if(g[i][j].from==i && marked[g[i][j].to]!=1){
                        cutCapacity+=g[i][j].flow;
                }
   }
   if(i==SOURCE)break;
 }
 return cutCapacity;
}

int main(){
    int N;

    scanf("%d", &N);
 N = N+2;
 SINK = N-1;
 g.reserve(N);
 for(int i=0;i<N;++i){
  vector<Edge> vec;
  vec.reserve(N);
  g.push_back(vec);
 }

    for(int i=1;i<=SINK-1;++i){
   scanf(" %d", &Mi[i-1]);
            Edge edge(SOURCE, i, Mi[i-1]);
            g[SOURCE].push_back(edge);
            g[i].push_back(edge);
    }
    for(int i=1;i<=SINK-1;++i){
   scanf(" %d", &Vi[i-1]);
            Edge edge(i, SINK, Vi[i-1]);
            g[i].push_back(edge);
            g[SINK].push_back(edge);
    }

    for(int i=1;i<=SINK-1;++i){
        for(int j=1;j<=SINK-1;++j){
   int t;
   scanf(" %d", &t);
            if(t!=0){
                Edge edge(i, j, t);
                g[i].push_back(edge);
                g[j].push_back(edge);
            }
        }
    }

    //Input ends
    printf("%d\n", fulkerson());
    return 0;
}