# Maximum weight matching with repeated nodes

We are given two sets of nodes $$A$$ and $$B$$ forming a graph where each element $$x \in A$$ can be connected with an element $$y \in B$$ with different possible weights. The graph can be explained in two ways.

1. There are multiple edges possible between elements of $$X$$ and $$Y$$ having different weights.

2. Elements of $$A$$ can be matched with repeated nodes of elements of $$B$$ with different edge weights.

Let $$E(x)$$ be the set of edges involving element x. Then the maximum weight matching problem can be formulated as follows:

Let $$x_{ij}$$ takes value 1, if edge $$(i, j) \in E$$ is selected and $$w_{ij}$$ be weight of edge $$(i, j) \in E$$.

$$\text{minimize} \sum_{(i, j) \in E} x_{ij}w_{ij}$$ $$\sum_{j \in E(i)}x_{ij} \le 1 \forall i \in A$$ $$\sum_{i \in E(j)}x_{ij} \le 1 \forall j \in B$$ $$x_{ij} = \{0, 1\} \quad \forall (i, j) \in E$$

My question is whether this problem satisfy the total unimodularity condition. If it does, how can we prove it? I know proof for the standard problem where you consider submatrices and find the determinant.

Can we still use network flow algorithms to solve this problem?