## MinCost MaxFlow code

**Moderator:** Board moderators

http://citeseer.ist.psu.edu/goldberg92efficient.html

I have implemented it (without the heuristics) and tested it on problem 10746. See:

http://www.cs.utexas.edu/~apetrov/acm/alg/mcmf/

### Re: MinCost MaxFlow code

I have a problem on UVA 3562... I used Igor's code to find the min cost, and then negated all the edges. I tried to use BellmanFord algorithm to find every circle with negative cost, and delete them. So, At last, my algorithm could get the max cost. But, I got WA and my program ran really slowly - 2~3 seconds for the max test data. I didn't know the matter...

PS. I even typed a program using KM to check the answer, and didn't find any problems. So, can anyone help me for the problem?

My Email address is sunzheng.david@163.com.

PS. I even typed a program using KM to check the answer, and didn't find any problems. So, can anyone help me for the problem?

My Email address is sunzheng.david@163.com.

### Re: MinCost MaxFlow code

I'm really sorry that I've made a strange mistake. I initialized the array with a large number 9e20. It has been so large that little changes (like 1e-2) would not be counted. So, after I changed 9e20 into 9e6, I got accepted...davidsun wrote:I have a problem on UVA 3562... I used Igor's code to find the min cost, and then negated all the edges. I tried to use BellmanFord algorithm to find every circle with negative cost, and delete them. So, At last, my algorithm could get the max cost. But, I got WA and my program ran really slowly - 2~3 seconds for the max test data. I didn't know the matter...

PS. I even typed a program using KM to check the answer, and didn't find any problems. So, can anyone help me for the problem?

My Email address is sunzheng.david@163.com.

### Min-Cost Max-Flow Related Problems

Hi everybody,

I collected some advanced graph problems. Maybe you need them for exercises.

00563 Crimewave ------------------------ (Vertices have capacity. Edges have not.)

00820 Internet Bandwidth

10330 Power Transmission -------------- (Vertices have capacity.)

10511 Councilling ------------------------- (Vertices have capacity.)

10779 Collectors Problem ---------------- (Vertices have capacity.)

10594 Data Flow

00259 Software Allocation

00663 Sorting Slides

00670 The Dog Task

00753 A plug for Unix

10080 Gopher II

10092 The Problem with the Problemsetter

10243 Fire! Fire!! Fire!!!

10418 Hyper Toy Soldiers

10735 Euler Circuit

10984 Double NP-hard

10122 Mysterious Mountain

10804 Gopher Strategy ------------------- (We can simply use Binary Search for the Min-Cost.)

10746 Crime Wave - The Sequel

10888 Warehouse ------------------------- (Dynamic Programming is allowed.)

10380 Shogi Tournament

10911 Forming Quiz Teams ------------- (Dynamic Programming is allowed.)

10480 Sabotage --------------------------- (Min-Cut Max-Flow Theorem can be used.)

10989 Bomb, Divide and Conquer

I collected some advanced graph problems. Maybe you need them for exercises.

**Max-Flow**00563 Crimewave ------------------------ (Vertices have capacity. Edges have not.)

00820 Internet Bandwidth

10330 Power Transmission -------------- (Vertices have capacity.)

10511 Councilling ------------------------- (Vertices have capacity.)

10779 Collectors Problem ---------------- (Vertices have capacity.)

**Min-Cost Max-Flow**10594 Data Flow

**Bipartite Matching**00259 Software Allocation

00663 Sorting Slides

00670 The Dog Task

00753 A plug for Unix

10080 Gopher II

10092 The Problem with the Problemsetter

10243 Fire! Fire!! Fire!!!

10418 Hyper Toy Soldiers

10735 Euler Circuit

10984 Double NP-hard

**Min-Cost Bipartite-Matching**10122 Mysterious Mountain

10804 Gopher Strategy ------------------- (We can simply use Binary Search for the Min-Cost.)

10746 Crime Wave - The Sequel

10888 Warehouse ------------------------- (Dynamic Programming is allowed.)

**Matching**10380 Shogi Tournament

**Min-Cost Matching**10911 Forming Quiz Teams ------------- (Dynamic Programming is allowed.)

**Min-Cut**10480 Sabotage --------------------------- (Min-Cut Max-Flow Theorem can be used.)

10989 Bomb, Divide and Conquer