International Oil Transport

Computer Science Level 3

Monroe Republic ( Vertex 0 ) has large reserves of gasoline. It has set up a large international network of pipelines all over the continent, with some hubs ( Vertices 1, 2, 3, 4 ). Due to several political reasons, the pipelines are fitted with valves and can support flow only in specific directions ( denoted with arrows ). The pipelines also have fixed capacities ( denoted by weights ) which are the maximum amounts of gasoline that can flow in megaliters per day.

Kyrat ( Vertex 5 ) has recently joined the network and wants to import gasoline from Monroe.

What is the maximum amount of gasoline that can be sent from Monroe to Kyrat per day in megaliters?


The answer is 14.

Agnishom Chattopadhyay by Agnishom Chattopadhyay , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Using the Floyd Warshall's Algorithm, O ( V 2 ) O(V^{2}) 

 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
 
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 6
#define INF 999999

int f, s, t, mf;
int res[MAX_N][MAX_N];
vector< vector<int> > AdjList;
vector<int> p;

void augment(int v, int minEdge){
    if(v==s){ f = minEdge; return;}
    else if(p[v]!=-1) {
        augment(p[v], min(minEdge, res[p[v]][v]));
        res[p[v]][v] -=f; res[v][p[v]] += f;
    }
}


int main(){

s = 0;
t = 5;

AdjList.push_back({1,2});
AdjList.push_back({3});
AdjList.push_back({4});
AdjList.push_back({4,5});
AdjList.push_back({1,5});
AdjList.push_back({});

for(int i=0; i<MAX_N; i++)
for(int j=0; j<MAX_N; j++)
res[i][j] = 0;

res[0][1] = 20;
res[0][2] = 10;
res[2][4] = 7;
res[4][1] = 4;
res[1][3] = 11;
res[3][4] = 5;
res[3][5] = 13;
res[4][5] = 3;

while(1){
    f = 0;
    bitset<MAX_N> vis; vis[s] = true;
    queue<int> q; q.push(s);
    p.assign(MAX_N,-1);
    while (!q.empty()){
        int u = q.front(); q.pop();
        if(u==t) break;
        for(int j=0; j<(AdjList[u].size()); j++){
            int v = AdjList[u][j];
            if(res[u][v]>0&&!vis[v]){
                vis[v] = true; q.push(v); p[v] = u;
            }
        }
    }

augment(t, INF);
if(f==0) break;
mf+=f;
}

cout << "Maximum Flow: " << mf << endl;

}

1 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...