MinCost MaxFlow code
Moderator: Board moderators
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.
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/
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.
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
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