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;↵
}↵
~~~~~↵
↵
↵
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;↵
}↵
~~~~~↵
↵
