Revenge of Minimum Cost Flow