**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", ®[i]); else {scanf("%d", ®[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