MinCost MaxFlow code

[sclo]

Use adjacency lists instead of matrix for the graph representation. The modification is quite trivial. But for that to work, for each edge from u->v with capacity c, and cost p, there must be a corresponding opposite edge from v->u with capacity 0 and cost -p. Also, it should be possible to look up the opposite edge in constant time. Let f be the current flow from u->v, then c-f is the capacity on the residual network. Everytime we increase the flow by f on u->v, we also decrease the flow by f on the corresponding opposite edge.

[serur]

lookup the back edge in constant time

Hm.. I should have some pointers to edges (in C) then.
A few mincost maxflows from LA:
2927 - 'Shortest pair'
3550 - 'Hotel'
(I didn't try as yet, though)

[apetrov87]

There is also a mincost maxflow algorithm based on the push-relabel idea:
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/

[davidsun]

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.

[davidsun]

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.

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...

[DJWS]

Hi everybody,
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