Блог

Я хотел бы спросить, может ли кто-нибудь сказать мне, что не так с моим кодом. Я пытаюсь решить проблему BerSU Ball на codeforces с Эдмондом-Карпом (я знаю о жадном солне)

Проблема: https://codeforces.com/problemset/problem/489/B

Я получаю неправильный ответ на тест 37. Я не могу найти свою ошибку. Вот моя реализация (код чистый, адаптированный из cp-алгоритмов)

 #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 viiamp; graph , viiamp; capacity);
int main(){
    int n;
    scanf("%d",amp;n);
    vi boys(n); 

    for(int i = 0 ; i <n ;i  ){
        scanf("%d",amp;boys[i]);
    }
    int m;

    scanf("%d",amp;m);
    vi girls(m);
    for(int i = 0 ; i < m ;i  ){
        scanf("%d",amp;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 viiamp; graph , viiamp; capacity , viamp; 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 amp;amp; 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 viiamp; graph , viiamp; 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;
}