Algorithm-and-Data-Structure/AlgorithmCode/MinCostMaxFlow.java at master · lemidia/Algorithm-and-Data-Structure · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
importjava.util.*;
importjava.util.LinkedList;

publicclassMinCostMaxFlow {

staticintn;
staticintm;
staticintsource;
staticintsink;
staticArrayList<Edge>[] flowGraph;
staticEdgeprev[];
staticintdist[];
staticbooleanonQueue[];
staticfinalintINF = Integer.MAX_VALUE;
staticintmaxFlow;
staticintminCostMaxFlow;

staticvoidcreateGraph(){
prev = newEdge[n];
dist = newint[n];
onQueue = newboolean[n];
flowGraph = newArrayList[n];
for (inti = 0; i < n; i++) {
flowGraph[i] = newArrayList<>();
 }
 }

staticvoidaddEdge(intfrom, intto, intcapacity, intcost){
Edgee1 = newEdge(from, to, 0, capacity, cost);
Edgee2 = newEdge(to, from, 0, 0, -1 * cost);
e1.backward = e2;
e2.backward = e1;
flowGraph[from].add(e1);
flowGraph[to].add(e2);
 }

staticintremainingCapacity(Edgee){
returne.capacity - e.flow;
 }

staticvoidaugment(Edgee, intbottleNeck){
minCostMaxFlow += e.cost * bottleNeck;
e.flow += bottleNeck;
e.backward.flow -= bottleNeck;
 }

// Shortest Path Faster Algorithm is used.
staticvoidgetMinCostMaxFlow(){
while (true) {
Arrays.fill(dist, INF);
prev[sink] = null;
Deque<Integer> queue = newLinkedList<>();
queue.offer(source);
onQueue[source] = true;
dist[source] = 0;
while (!queue.isEmpty()) {
intcur = queue.poll();
onQueue[cur] = false;
for (Edgee : flowGraph[cur]) {
intnewDist = e.cost + dist[cur];
// Remaining Capacity and Unvisited and Can be Edge Relaxation
if (remainingCapacity(e) > 0 && newDist < dist[e.to]) {
dist[e.to] = newDist;
prev[e.to] = e;
if (!onQueue[e.to]) {
onQueue[e.to] = true;
queue.offer(e.to);
// Small Label First
if (dist[e.to] < dist[queue.peekFirst()]) {
queue.offerFirst(queue.pollLast());
 }
 }
 }
 }
 }
if (prev[sink] == null)
break;
intbottleNeck = INF;
for (Edgee = prev[sink]; e != null; e = prev[e.from]) {
intremainingCapacity = remainingCapacity(e);
if (remainingCapacity < bottleNeck)
bottleNeck = remainingCapacity;
 }

for (Edgee = prev[sink]; e != null; e = prev[e.from]) {
augment(e, bottleNeck);
 }
maxFlow += bottleNeck;
 }
 }

// test module
publicstaticvoidmain(String[] args) {
n = 6;
source = n-1;
sink = n-2;
createGraph();
addEdge(source, 1, 4, 10);
addEdge(source, 2, 2, 30);
addEdge(1, 2, 2, 10);
addEdge(1, sink, 0, 9999);
addEdge(2, sink, 4, 10);

getMinCostMaxFlow();

System.out.println(maxFlow + " " + minCostMaxFlow);
 }

staticclassEdge{
intfrom;
intto;
intflow;
intcapacity;
intcost;
Edgebackward;

publicEdge(intfrom, intto, intflow, intcapacity, intcost) {
this.from = from;
this.to = to;
this.flow = flow;
this.capacity = capacity;
this.cost = cost;
 }
 }
}