In a standard s ? t Maximum-Flow Problem, we assume edges have capacities, and there is no limit on how much flow is allowed to pass through a node. In this problem, we consider a variant of the Maximum-Flow and Min-Cut problems with node capacities.

Let G = (V, E) be a directed graph, with source s ? V , sink t ? V , and nonnegative node capacities cv ?0 for each v?V. Given a flow f in this graph,the flow through node v is defined as fin(v). We say that a flow is feasible if it satisfies the usual flow-conservation constraints and the node-capacity constraints: fin(v) ? cv for all nodes.

Give a polynomial-time algorithm to find an s ? t maximum flow in such a node-capacitated network. Define an s?t cut for node-capacitated networks, and show that the analogue of the Max-Flow Min-Cut Theorem holds true.