max matching with Edmond Karp

Viewed 42

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;
}
0 Answers
Related