Problem statement
Given a graph with $$$n$$$ nodes and $$$m$$$ edges,
- Find a path that starts at a node (the node is not specified).
- Visit each edge at least once.
- End the path at the starting node.
- Minimize the total cost of the tour.
Input
- The number of nodes $$$n$$$ : $$$2 \leq n \leq 20$$$
- The number of edges $$$m$$$ : $$$1 \leq m \leq 100$$$.
- For each edge, provide the source node, destination node, and the cost associated with that edge.
Output
Output the minimum cost of a tour that satisfies the conditions mentioned above.
Note
The path must visit each edge at least once (meaning you can pass the number of time you want), and the tour must end at the starting node.
Can the problem be solved using :
- $$$dp$$$ with bitmask?
- min cost max flow?
If you have any solution feel free to comment on it. Thanks!!!
Question: is the graph weighted since it's asking for cost?
Yes. I have mentioned it as the third point of the input.
Where is this task from?
This is the directed version of the Chinese postman problem, which could be solved in O(V2E) via MCMF.
Sorry I get fever and reply to you via a mobile phone on a bed. Search the problem on wiki yourself plz.
Thanks for your feedback. I found that name somehow yesterday but just realized it is the same. But the approach used for solving it involved minimum weighted perfect matching and Euler tour not MCMF or do it? Also, is there any possible $$$dp$$$ solution for this problem?