So I have recently ran into a graph theory problem and was unable to find a matching algorithm for the problem or reword the problem to match some existing algorithm.
The problem is pretty straightforward - given a weighted directed graph, pick edges to maximize the sum of all weights of the chosen edges. Max one edge can point to another vertex and no vertex can be the head for more than one edge.
So far this would seem like a problem solvable with a matching algorithm, but there's an extra catch - a vertex can be the head for an edge only if the vertex is not a tail of any edges in the initially given graph, or if it's a tail for one of the chosen edges. On top of that, the graph from the chosen edges has to be acyclic.
A good analogy would be to imagine each vertex as a cell. I can mark all vertices that are initially tails of some edges as cells with some object in them. Picking an edge would mean moving the object from one cell to another. This analogy seems perfect, because:
A vertex can be the tail of max one chosen edge(aka the object can be moved to only one other cell)
A vertex can be the head of max one chosen edge(aka only one object can be moved into a cell)
A vertex can be the head for a selected edge only if the vertex was not a tail of any edges in the initially provided graph, or if it's a tail for one of the chosen edges(aka the cell was either initially empty or the object can be carried into another cell thus emptying the cell)
As good as it is, I was unable to find any algorithms that would be of any help. Is pure bruteforcing for edge combinations as good as it gets? Or can I get the edges in a more optimized way?