Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a marriage can be set up among the corresponding man and women.
Each broker $i$ can set up a maximum of $b_i$ marriages and a person can only be married once. Also we assume all marriages are heterosexual.
I want to determine the maximum number of marriages possible and I want to show that the answer can be found be solving a maximum-flow problem.
What I've tried:
Make source and sink nodes with opposite demand. And then for each ordered pair $(i,j)$ where $i$ is a woman and $j$ is a man making a node. For each broker $j$ make a corresponding node and introduce an arc with capcity $b_j$. For each node $(i,j)$ make an arc from broker $k$ with capacity $1$ if broker $k$ can arrange a marriage otherwise $0$.
However, after this I stop. I need to keep track of state, that is no person gets married twice !
Best Answer
You can represent each man, woman, and broker by an edge and two vertices.
Consider the following vertices. Source $A$, sink $Z$. For every man, we have vertices $M_j$ and $M'_j$ with $j \in \{1,\ldots,n\}.$ Similarly, for every woman, we haven vertices $W_j$ and $W'_j$ with $j \in \{1,\ldots,n\}.$ And for every broker, we have vertices $B_j$ and $B'_j$ with $j \in \{1,\ldots,m\}.$
Now connect the vertices as follows. Edges $(A,M_j)$ with capacity $\infty$ for every man, these capacities are not important. Edges $(M_j,M'_j)$ with capacity $1$ for every man, these capacities ensure that every man gets married at most once. Edges $(M'_j,B_k)$ iff the $j$-th man works with the $k$-th broker. These edges have capacity $\infty$ (not important). Edges $(B_j,B'_j)$ with capacity $b_j$ for every broker, these capacities ensure that this broker arranges at most $b_j$ marriages. Edges $(B'_j,W_k)$ iff the $k$-th woman works with the $j$-th broker. These edges have capacity $\infty$ (not important). Edges $(W_j,W'_j)$ with capacity $1$ for every woman, these edges ensure that every woman gets married at most once. Edges $(W'_j,Z)$ with capacity $\infty$ for every woman, these capacities are not important.
If you look at this graph for a very short time, you will realize that the maximum possible flow is $n$. And if we can find a flow of that size, then every man and every woman is married excatly once, since through each edge $(M_j,M'_j)$ and $(W_j,W'_j)$ we must have a flow of size $1$, and furthermore the $j$-th broker arranges at most $b_j$ marriages, since through each edge $(B_j,B'_j)$ we have a flow of size at most $b_j$.
This graph can be simplified. But the principle is that if you want to restrict the flow through a vertex, you replace this vertex with two connected vertices and give the new edge between those vertices the desired capacity.