hi!
I was trying to solve this problem 1424B - Valuable Paper 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 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;
}
