Bioinformatics_Algorithms/MaxFlowMinCost.py at main · iManGHD/Bioinformatics_Algorithms · 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
126
127
128
129
130
131
132
133
134

# Max Flow Min Cost

# found edges
found = []

# number of nodes
N = 0

# capacity of each edge
cap = []

flow = []

# cost each node
cost = []

# distance from each node
dad = []
dist = []
pi = []

INF = 999999999999999


def search(src, sink):
    found = [False for _ in range(N)]
    dist = [INF for _ in range(N + 1)]
    dist[src] = 0
    while (src != N):
        best = N
        found[src] = True

        for k in range(N):

            if (found[k]):
                continue

            if (flow[k][src] != 0):

                val = (dist[src] + pi[src] -
                       pi[k] - cost[k][src])

                if (dist[k] > val):
                    dist[k] = val
                    dad[k] = src

            if (flow[src][k] < cap[src][k]):
                val = (dist[src] + pi[src] -
                       pi[k] + cost[src][k])

                if (dist[k] > val):
                    dist[k] = val
                    dad[k] = src

            if (dist[k] < dist[best]):
                best = k

        src = best

    for k in range(N):
        pi[k] = min(pi[k] + dist[k], INF)

    return found[sink]


# Max Flow
def maxFlow(capi, costi, src, sink) :
    global cap, cost, found, dist, pi, N, flow, dad
    cap = capi
    cost = costi

    N = len(capi)
    found = [False for _ in range(N)]
    global flow
    flow = [[0 for _ in range(N)]
            for _ in range(N)]
    dist = [INF for _ in range(N + 1)]
    dad = [0 for _ in range(N)]
    pi = [0 for _ in range(N)]

    totflow = 0
    totcost = 0

    while (search(src, sink)):
        amt = INF
        x = sink

        while x != src:
            amt = min(
                amt, flow[x][dad[x]] if
                (flow[x][dad[x]] != 0) else
                cap[dad[x]][x] - flow[dad[x]][x])
            x = dad[x]
        x = sink
        while x != src:
            if flow[x][dad[x]] != 0:
                flow[x][dad[x]] -= amt
                totcost -= amt * cost[x][dad[x]]
            else:
                flow[dad[x]][x] += amt
                totcost += amt * cost[dad[x]][x]
            x = dad[x]
        totflow += amt

    return [totflow, totcost]


if __name__ == "__main__":

    V, E = map(int, input().split())
    Capacity = [[0] * V for _ in range(V)]
    Cost = [[0] * V for _ in range(V)]
    for i in range(E):
        x, y, cap, cos = map(int, input().split())
        Capacity[x][y] = cap
        Cost[x][y] = cos

    source = 0
    sink = V - 1

    ret = maxFlow(Capacity, Cost, source, sink)

    # ret[0] : Max Flow
    # ret[1] : Min Cost
    print("{} {}".format(ret[0], ret[1]))

    # Print : First Vertex    Second Vertex    Transient current rate

    for i in range(V):
        a = []
        for j in range(V):
            if Capacity[i][j] > 0:
                print(i, j, flow[i][j])