I'd please like to ask if someone can please tell me whats wrong with my code. I'm trying to solve the problem BerSU Ball on codeforces with Edmond-Karp (I'm aware of the greedy soln)
Problem: https://codeforces.com/problemset/problem/489/B
I'm getting a wrong answer on test 37. I'm not able to find my mistake. Here is my implementation (The code is clean - adapted from cp-algorithms)
#include<vector>
#include<iostream>
#include<queue>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vii;
const int INF=1e9+5;
int maxflow(int source, int sink , const vii& graph , vii& capacity);
int main(){
int n;
scanf("%d",&n);
vi boys(n);
for(int i = 0 ; i <n ;i++){
scanf("%d",&boys[i]);
}
int m;
scanf("%d",&m);
vi girls(m);
for(int i = 0 ; i < m ;i++){
scanf("%d",&girls[i]);
}
int len = n+m+2;
int source = len-2;
int sink = len-1;
vii graph(len);
vii capacity(len , vi(len,0));
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
if(abs(boys[i]-girls[j]) <= 1){
graph[i].push_back(j+n);
graph[n+j].push_back(i);
capacity[i][j+n]=1;
capacity[j+n][i]=1;
}
}
}
for(int i = 0 ; i < n ;i++){
graph[i].push_back(source);
graph[source].push_back(i);
capacity[i][source]=1;
capacity[source][i]=1;
}
for(int i = 0 ; i < m ; i++){
graph[sink].push_back(n+i);
graph[n+i].push_back(sink);
capacity[sink][n+i]=1;
capacity[n+i][sink]=1;
}
// for(int i = 0 ; i < len; i++){
// cout << i << " : ";
// for(int j = 0 ; j < len ; j++){
// cout << capacity[i][j] << " ";
// }
// cout << endl;
// }
cout << maxflow(source,sink,graph,capacity) << endl;
return 0;
}
int bfsEdmond(int source , int sink , const vii& graph , vii& capacity , vi& parent){
int len = (int)graph.size();
parent.assign(len,-1);
parent[source]=-2;
queue<pair<int,int>>q;
q.push({source,INF});
while(!q.empty()){
int cnode = q.front().first;
int cflow=q.front().second;
q.pop();
//cout << "exploring " << cnode << endl;
for(int next: graph[cnode]){
//cout << next << " " << endl;
if(parent[next] == - 1 && capacity[cnode][next]){
// explore adjacency list
parent[next]=cnode;
int newflow = min(cflow,capacity[cnode][next]);
if(next == sink){
return newflow;
}
q.push({next,newflow});
}
}
}
return 0;
}
int maxflow(int source, int sink , const vii& graph , vii& capacity){
int len = (int)graph.size();
vi parent(len);
int maxx=0;
int cflow=0;
while( (cflow = bfsEdmond(source,sink,graph,capacity,parent))){
maxx+=cflow;
int cnode = sink;
while(cnode!=source){
int prev = parent[cnode];
capacity[prev][cnode]-=cflow;
capacity[cnode][prev]+=cflow;
cnode=prev;
//cout << "dine " << endl;
}
}
return maxx;
}