Thursday, January 21, 2016

SPOJ (COCONUTS) - Mincut - Solution C++

Problem : COCONUTS

Algorithm:

1. Add SOURCE and SINK nodes.
2. Add an edge from SOURCE to guard for those guards who say YES (Group A). Directed edge with capacity 1.
3. Add an edge from Guard node to SINK node for those guards who say NO (Group B). Directed edge with capacity 1.
4. Guards who are friends will have bidirectional edges with capacity 1.
5. Determine the mincut capacity (=ans). 

Any outgoing edge from source to Group A that is counted as mincut capacity means a change of opinion of those who say YES to NO.
Any outgoing edge from Group B to SINK that is counted as mincut capacity means a change of opinion of those who say NO to YES.
Any outgoing edge from Group A to Group B or reverse that is counted as mincut capacity means a clash of opinion.

Adding all these, mincut capacity gives the minimum possible sum of (clash of opinions+change of opinions).

For each outgoing edge from Group

Source (Ford-Fulkerson algorithm for Mincut):

#include <stdio.h>
#include <queue>
#define DEBUG 0

using namespace std;

int nGuards, nPairs;

const int MAX = 302;
int graph[MAX][MAX];
int reg[MAX];
int SOURCE =0;
int SINK;

int mincut();
int augmentingPathExists();

int main(){

        FILE* file;
        if(DEBUG)file = fopen("d:\\input.txt", "r");
        while(1){
            if(DEBUG) fscanf(file, "%d %d", &nGuards, &nPairs);
            else scanf("%d %d", &nGuards, &nPairs);

            if(nGuards==0 && nPairs==0)return 0;
            SINK = nGuards+1;


            for(int i=0;i<=nGuards;++i) for(int j=0;j<=nGuards+1;++j)graph[i][j] = -1;

            for(int i=0;i<=nGuards+1;++i)reg[i] = 0;
            for(int i=1;i<=nGuards;++i){
                if(DEBUG)fscanf(file, "%d", &reg[i]); else {scanf("%d", &reg[i]);}
                if(reg[i]==1)graph[SOURCE][i] = 1;
                else graph[i][SINK] = 1;
            }

            for(int i=0;i<nPairs;++i){
                int a, b;
                if(DEBUG)fscanf(file,"%d %d", &a, &b);else {scanf("%d %d", &a, &b);}
                graph[a][b] = 1;
                graph[b][a] = 1;
            }
            printf("%d\n", mincut());
 }
 return 0;
}

int path[MAX];

int augmentingPathExists(){
 queue<int> q;
 for(int i=0;i<nGuards+2;++i)path[i] = -1;
 for(int i=0;i<nGuards+2;++i)reg[i] = 0;

 bool stop = false;

 q.push(SOURCE);
 reg[SOURCE] = 1;
 int v;
 while(!q.empty()){
  v = q.front();
  q.pop();

  for(int i=1;i<=nGuards+1;++i){
   if(reg[i]!=1){
    if(graph[v][i]==1 || (i!=SINK && graph[i][v]==0)){
     reg[i] = 1;
     if(path[i]==-1)path[i] = v;
     if(i == SINK){
      stop = true;
      v = SINK;
      break;
                    }
     q.push(i);
    }
   }
  }
  if(stop)break;
 }
 return v;
}

int mincut(){
 int v = augmentingPathExists();
 int flow=0;
 while(v==SINK){
  for(int i=v;i!=SOURCE;i = path[i]){
   if(graph[path[i]][i]==1){
    graph[path[i]][i]=0;
   }
   else if(graph[i][path[i]]==0){
    graph[i][path[i]]=1;
   }
  }
  flow++;
  v = augmentingPathExists();
 }

 int cutCapacity=0;
 for(int i=SINK;i>=0;--i){
   if(reg[i]!=1)continue;
   for(int j=1;j<=nGuards+1;++j){
    if(reg[j]==0 && graph[i][j]==0){
                        cutCapacity++;
                }
   }
   if(i==0)break;
 }
 return cutCapacity;
}

No comments:

Post a Comment