could someone give me an algorithm of the minimal cost matching in chinese postman problem?
i saw some webpage says that there is a O(n+3) algorithm but it didn't provide it...
about chinese postman problem
Moderator: Board moderators
I assume you mean Chinese Postman in an undirected graph. This reduces to min-cost general (non-bipartite) matching. There's a polytime algorithm, but it is incomprehensible to most humans and I'm not aware of any simple implementation. If somebody has a simple implementation, I would be delighted to see it.
If the graph is directed, it reduces to min-cost bipartite matching. Still a bit of code, but within the realm of possibility in a programming contest.
If the graph is directed, it reduces to min-cost bipartite matching. Still a bit of code, but within the realm of possibility in a programming contest.
my approach..
I usually (well, all the time) implement this part using backtracking and so far have managed to avoid TLE..
It works fine for 13/14 nodes, but for higher values i don't think backtracking will suffice.
How does everyone else implement this part.. backtracking or something else..
when i say 'this part' i mean minimal cost matching.
It works fine for 13/14 nodes, but for higher values i don't think backtracking will suffice.
How does everyone else implement this part.. backtracking or something else..
when i say 'this part' i mean minimal cost matching.