Consider a simple weighted digraph $G=(V, E)$ with the vertex set $V=\{1,\cdots, n\}$ and the edge set $E$. Each edge $(i,j)\in E$ is endowed with a positive weight $w_{ij}$. Let $|\ S \ |$ denote the cardinality of any set $S$. The set of vertices pointing to $i$ is denoted by $N^{-}(i,G)=\{j: (j,i)\in E\}$, and similarly that out of $i$ by $N^{+}(i,G)=\{j: (i,j)\in E\}$. Indegrees and outdegrees of the vertex $i$ are denoted by $\Delta^{-}(i)=|N^{-}(i,G)|$ , $\Delta^{+}(i)=|N^{+}(i,G)|$ respectively. Let $\Delta(i)=\min(\Delta^{-}(i),\Delta^{+}(i))$ and $\Delta=\min_{i\in
V}\Delta(i)$. $G$ is called $\alpha n$ dense if $\Delta\geq\alpha n$ for an $\alpha>0$ given. Let $\oplus$ denote the symmetric difference of two sets and $\lfloor n\rfloor$ denote the maximum integer no more than $n$. $A/B$ is used to denote the set by removing elements of $B$ from the set $A$. With a little abuse of notation, $/$ also denote the quotient of two numbers. A Hamiltonian cycle in $G$ is represented by

$\mathcal {H}=(k_1,k_2,\cdots, k_n,k_1)$,

where $\{k_1,k_2,\cdots, k_n\}$ is a permutation of $\{1,\cdots,n\}$ such that $(k_n,k_1)\in E$, and$(k_j,$ $k_{j+1})$ $\in E$, $j=1,\cdots, n-1$. The length of a cycle or path is defined as the number of its edges that contains.

An 1-factor is defined as a spanning directed 