Complexity of the Kitten Adoption problem
This is the min-cost max-flow problem.

Consider a graph $G=(A\cup B\cup \{s,t\},E)$, where $A$ is the set of kittens, $B$ is the set of people. 

Let $C:E\to \mathbb{R}^+$ be the capacity of the edges, and $c:E\to \mathbb{R^+}$ be the cost of an edge. We make sure that


There is an edge between $a_i,b_j$, where $a_i\in A$ and $b_j\in B$, and $C(a_i,b_j)=1$, $c(a_i,b_j)=c_{i,j}$.
There is an edge between $s$ and $a_i\in A$, and $C(s,a_i)=1$, $c(s,a_i)=0$.
There is an edge between $b_j\in B$ and $t$, and $C(b_j,t)=u_j$, $c(b_j,t)=0$.


If the max flow is $M$, then we know there exist a solution. You can construct a min-cost solution from the min-cost max-flow.