I need to find a cost-optimal 1-factor in a positively weighted, directed, regular graph $G(V,A)$ without antiparallel arcs, i.e. given $$\text{deg}_{\text{in}}(u)=\text{deg}_{\text{in}}(v)=\text{deg}_{\text{out}}(v)=\text{deg}_{\text{out}}(u)\ \ \forall u,v\in V$$ $$a_{ij}\in G\implies a_{ji}\notin G$$ $$c_{ij}:= c(a_{ij}) \gt 0$$

determine $\alpha_{ij}\in\lbrace 0,1\rbrace$, so that $$\sum_j{\alpha_{ij}}=\sum_i{\alpha_{ij}}=1$$ and $$\sum{\alpha_{ij}c_{ij}} = \text{opt}$$
That problem can be easily solved without the integer constraints via linear programming.

It is also possible to solve it via negative cycle cancellation after vertex splitting.

Question:

 

can the above problem be solved without linear programming and without vertex splitting, using one of the graph theoretic algorithms for mincost flows?

I need to find a cost-optimal 1-factor in a positively weighted, directed, regular graph $G(V,A)$ without antiparallel arcs, i.e. given $$\text{deg}_{\text{in}}(u)=\text{deg}_{\text{in}}(v)=\text{deg}_{\text{out}}(v)=\text{deg}_{\text{out}}(u)\ \ \forall u,v\in V$$ $$a_{ij}\in G\implies a_{ji}\notin G$$ $$c_{ij}:= c(a_{ij}) \gt 0$$

determine $\alpha_{ij}\in\lbrace 0,1\rbrace$, so that $$\sum_j{\alpha_{ij}}=\sum_i{\alpha_{ij}}=1$$ and $$\sum{\alpha_{ij}c_{ij}} = \text{opt}$$
That problem can be easily solved without the integer constraints via linear programming.

It is also possible to solve it via negative cycle cancellation after vertex splitting.

Question:

can the above problem be solved without linear programming and without vertex splitting, using one of the graph theoretic algorithms for mincost flows?