Created
November 17, 2019 21:05
Star
You must be signed in to star a gist
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import "fmt" | |
const ( | |
white = 0 | |
blue = 1 | |
red = 2 | |
) | |
type airportsQueue struct { | |
O, D int | |
queue, color []int | |
} | |
func (queue *airportsQueue) init(airport int) { | |
queue.queue = make([]int, airport+2) | |
queue.color = make([]int, airport) | |
} | |
func (queue *airportsQueue) add(airport int) { | |
queue.queue[queue.D] = airport | |
queue.D++ | |
queue.color[airport] = blue | |
} | |
func (queue *airportsQueue) remove() int { | |
aux := queue.queue[queue.O] | |
queue.O++ | |
queue.color[aux] = red | |
return aux | |
} | |
type travel struct { | |
O int | |
D int | |
capacity int | |
} | |
type queueTravel []travel | |
type analysedFlux struct { | |
path []int | |
capacity int | |
} | |
type fordScheduler struct { | |
airportsV int | |
O int | |
D int | |
sits [][]int | |
pred []int | |
flow [][]int | |
} | |
// set the bigger value to compare on future | |
const maxSize = 99999 | |
func (schedulerFord *fordScheduler) bfs(start int, target int) bool { | |
var u, v int | |
q := &airportsQueue{O: 0, D: 0} | |
q.init(schedulerFord.airportsV + 1) | |
q.add(start) | |
schedulerFord.pred[start] = -1 | |
for q.O != q.D { | |
u = q.remove() | |
for v = 0; v < schedulerFord.airportsV; v++ { | |
if q.color[v] == white && schedulerFord.sits[u][v]-schedulerFord.flow[u][v] > 0 { | |
q.add(v) | |
schedulerFord.pred[v] = u | |
} | |
} | |
} | |
return q.color[target] == red | |
} | |
func min(input1 int, input2 int) int { | |
if input1 < input2 { | |
return input1 | |
} | |
return input2 | |
} | |
func (schedulerFord *fordScheduler) maxFlow() []analysedFlux { | |
var maxflowAux = 0 | |
var travelCount = make([]int, 0) | |
// used to calc number of days spent | |
indexFlowWithA := make([]analysedFlux, 0) | |
indexFlow := 0 | |
for schedulerFord.bfs(schedulerFord.O, schedulerFord.D) { | |
// increment is the number of Atletas that can be transported on the way | |
increment := maxSize | |
for u := schedulerFord.airportsV - 1; schedulerFord.pred[u] >= 0; u = schedulerFord.pred[u] { | |
increment = min(increment, schedulerFord.sits[schedulerFord.pred[u]][u]-schedulerFord.flow[schedulerFord.pred[u]][u]) | |
} | |
// Flow is the path will be filled by Atletas | |
aux := 0 | |
pathProvider := make([]int, 0) | |
for u := schedulerFord.airportsV - 1; schedulerFord.pred[u] >= 0; u = schedulerFord.pred[u] { | |
schedulerFord.flow[schedulerFord.pred[u]][u] += increment | |
schedulerFord.flow[u][schedulerFord.pred[u]] -= increment | |
pathProvider = append(pathProvider, u) | |
aux++ | |
} | |
indexFlowWithA = append(indexFlowWithA, analysedFlux{ | |
path: make([]int, aux), | |
capacity: 0, | |
}) | |
pathProvider = append(pathProvider, 1) | |
indexFlowWithA[indexFlow].path = pathProvider | |
indexFlowWithA[indexFlow].capacity = increment | |
travelCount = append(travelCount, increment) | |
maxflowAux += increment | |
indexFlow++ | |
} | |
return indexFlowWithA | |
} | |
func (schedulerFord *fordScheduler) findBiggerTravel(travels queueTravel) int { | |
// schedulerFord is a appointer to reiceve in another function the memory address | |
element := 0 | |
for _, travel := range travels { | |
if travel.O > element { | |
element = travel.O | |
} | |
if travel.D > element { | |
element = travel.D | |
} | |
} | |
return element | |
} | |
func (schedulerFord *fordScheduler) startNew(OInput int, DInput int, edges queueTravel) { | |
index := schedulerFord.findBiggerTravel(edges) + 1 | |
schedulerFord.airportsV = index | |
// create matriz to set graph sits (indicates during bfs) | |
// create matriz to set graph flow (indicates before bfs, on ford alg) | |
schedulerFord.sits = make([][]int, index) | |
schedulerFord.flow = make([][]int, index) | |
for i := range schedulerFord.sits { // dos not make difference use sits or flow (they have same size) | |
schedulerFord.flow[i] = make([]int, index) | |
schedulerFord.sits[i] = make([]int, index) | |
} | |
schedulerFord.O = OInput // origem input | |
schedulerFord.D = DInput // destination input, or sink, or target | |
schedulerFord.pred = make([]int, index) | |
for _, edge := range edges { | |
schedulerFord.sits[edge.O][edge.D] = edge.capacity | |
} | |
} | |
func readEntry() (int, int, int) { | |
var n, m, a int | |
_, _ = fmt.Scanf("%d %d %d", &n, &m, &a) // the _ is for ignore possible erors | |
// conditions from enunciado | |
if n < 2 || n > 50 { | |
return 0, 0, 0 | |
} | |
if m < 1 || m > 2450 { | |
return 0, 0, 0 | |
} | |
if a < 1 || a > 50 { | |
return 0, 0, 0 | |
} | |
return n, m, a | |
} | |
func readEntryLine(n int) (int, int, int) { | |
var o, d, s int | |
_, _ = fmt.Scanf("%d %d %d", &o, &d, &s) | |
// conditions from enunciado | |
if o < 1 || o > n { | |
return 0, 0, 0 | |
} | |
if (d < 1 || d > n) && o == d { | |
return 0, 0, 0 | |
} | |
if s < 1 || s > 50 { | |
return 0, 0, 0 | |
} | |
return o, d, s | |
} | |
func fordFulkersonAlgorithm(o int, d int, a queueTravel) []analysedFlux { | |
var funcCaller = &fordScheduler{} | |
// initialize caller with entrys | |
funcCaller.startNew(o, d, a) | |
// call max flow function (made embased in ford fulkerson alg) | |
return funcCaller.maxFlow() // return an array with the path and the capacity to transport Atletas (max flow) | |
} | |
func output(input []int){ | |
// output | |
for i:=0; i < len(input); i++{ | |
if len(input) == i+1{ | |
fmt.Print(input[i]) | |
}else{ | |
fmt.Println(input[i]) | |
} | |
} | |
} | |
func main() { | |
var daysSpentInTestCase = make([]int, 0) | |
for { | |
// read entrys | |
n, m, a := readEntry() | |
// N: Airports | |
// M: Travels avaible | |
// A: Atletas to travel | |
if n == m && m == a && a == 0 { | |
output(daysSpentInTestCase) | |
return | |
} | |
var i int | |
var tr = queueTravel{} | |
for i = 0; i < m; i++ { | |
o, d, s := readEntryLine(n) | |
// O: Origem (source) | |
// D: Destino (sink) | |
// S: Sits (Weigth of edge) | |
tr = append(tr, travel{O: o, D: d, capacity: s}) | |
} | |
// here we calculate Ford Fulkerson Max Flow | |
flux := fordFulkersonAlgorithm(1, n, tr) | |
// found the days necessary to transport all atletas | |
day := 1 | |
var reached int | |
for reached < a { | |
for i := 0; i < len(flux); i++ { | |
if day >= len(flux[i].path)-1 { | |
reached += flux[i].capacity | |
} | |
} | |
day++ | |
} | |
daysSpentInTestCase = append(daysSpentInTestCase, day-1) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment