## Thursday, January 21, 2016

### 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){
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;
}

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)){
}
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;
}```