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 14. 15. Exercises node. In this problem, we consider the variant of the Maximum-Flow and Minimum-Cut problems with node capacities. Let G = (V, E) be a directed graph, with source s ~ V; sink t ~ V, and normative node capacities {cu > 0} for each v ~ V. Given a flow f in this graph, the flow though a 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) _< Cu 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. solution