I've been searching for a while now, but did not succeed in finding whether the problem I have is actually a max-flow min-cut problem or it can be deduced to it, i.e. the algorithms that are used to solve max-flow min-cut problem will be suitable for solving this problem as well.
My problem is as follows:
$$ \text{minimize} \, \, \sum_{i=1}^n \sum_{j=1}^m d_{ij} w_{ij} \\ \text{subject to} \,\, \sum_{i=1}^n w_{ij} \le 1, \, \forall j \in \{1, \dots, m\} \\ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \, \sum_{j=1}^m w_{ij} \le 1, \, \forall i \in \{1, \dots, n\} \\ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \, \sum_{i=1}^n \sum_{j=1}^m w_{ij} = k \\ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \, w_{ij} \in \{0, 1\}, \,\, \forall (i,j) \in \{1, \dots, n\} \times \{1, \dots, m\} $$
Then it is not hard to show that the last set of constraints can be relaxed as $0 \le w_{ij} \le 1, \,\, \forall (i,j) \in \{1, \dots, n\} \times \{1, \dots, m\}$ and assuming the uniqueness of the solution of the initial problem the solution of the relaxed problem is indeed a solution to the initial problem.
My difficulty is with reformulation of constraint $\left(\sum_{i=1}^n \sum_{j=1}^m w_{ij} = k\right)$ because of $k$, other constraints seem to be fine. In fact, without this constraint the problem becomes the assignment problem, which can be solved using Hungarian algorithm, however the straightforward application of Hungarian algorithm is not possible here.
I know that this problem is a classic linear program, which can be solved efficiently using linear programming, however I'm curious whether this is indeed min-cut max-flow problem. If yes, how can I reformulate it (putting source and sink and corresponding weights) to be able to solve it as min-cut/max-flow?
You can formulate this as a minimum-cost network flow problem in a directed network with $n+m+2$ nodes and $n+nm+m$ arcs. The source node has supply $k$ and an arc with capacity $1$ to each $i$ node. The sink node has demand $k$ and an arc of capacity $1$ from each $j$ node. An arc from each $i$ node to each $j$ node has cost $d_{ij}$.