Hopcroft Karp BPM algorithm
Разница между en1 и en2, 684 символ(ов) изменены
hi!↵

I was trying to solve this problem [problem:1424B]↵
my solution was that I do a binary search on minimum cost and check if can I make a perfect match or not.↵
I wanted to use Hopcroft Karp BPM algorithm but I didn't understand the bfs part of the algorithm.↵
so I change the algorithm and use this code:↵

~~~~~↵
bool dfs(int v,int lastu=-1){↵
    for(int u:adj[v]){↵
        if(u==lastu)↵
            continue;↵
        if(match[u]==-1 || dfs(match[u],u) ){↵
            match[u] = v;↵
            return true;↵
    }↵
    return false;↵
}↵

bool check(){↵
    for(int i=0;i<n;i++){↵
        match[i] = -1;↵
    for(int i=0;i<n;i++)↵
        dfs(i);↵
    for(int i=0;i<n;i++)↵
        if(match[i]==-1)↵
             return false;↵
    return true;↵
}↵
~~~~~↵
match[i] is the vertex that i matches to.↵
dfs try to find an augmenting path and if one found,it will change match array and returns true. otherwise returns false.↵
check function is the main function and call dfs for each vertex and after that it checks if we have any non match vertex.↵

I think I've read something about this optimization before.but I didn't remember how exactly it is.↵

I think the code is correct but when I submit it I get Memory limit error. here is the submission [submission:94791415].↵

I'll be glad if anyone helps.↵

**Update**↵
I think i figure out why my code is wrong.to solve this problem we can delete lastu and instead get an array mark[i]↵
and set all elements false when want to start dfs.code is now like this:↵

~~~~~↵
bool dfs(int v,){↵
    mark[v] = true;↵
    for(int u:adj[v]){↵
        if(match[u]==-1 || (mark[match[u]]==0 && dfs(match[u],u) ) ){↵
            match[u] = v;↵
            return true;↵
    }↵
    return false;↵
}↵

bool check(){↵
    for(int i=0;i<n;i++){↵
        match[i] = -1;↵
    for(int i=0;i<n;i++){↵
        memset(mark,0,n);↵
        dfs(i);↵
    }↵
    for(int i=0;i<n;i++)↵
        if(match[i]==-1)↵
             return false;↵
    return true;↵
}↵
~~~~~↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский mohammad258 2020-10-05 20:44:17 684 change code
en1 Английский mohammad258 2020-10-05 19:49:35 1350 Initial revision (published)