airports_queue.go

package main

const WHITE = 0
const BLUE = 1
const 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
}

ford_fulkerson.go

package main

type Travel struct {
	tail int
	head int
	capacity int
}

type AnalysedFlux struct {
	path []int
	capacity int
}

type QueueTravel []Travel
const MaxSize = int(^uint(0) >> 1)

type fordScheduler struct {
	airportsV int
	O int
	D int
	sits [][]int
	pred []int
	flow [][]int
}

func (gs *fordScheduler) bfs(start int, target int) bool {
	var u, v int

	q := &AirportsQueue{O: 0, D: 0}
	q.Init(gs.airportsV + 1)

	q.add(start)
	gs.pred[start] = -1
	for q.O != q.D {
		u = q.remove()

		for v = 0; v < gs.airportsV; v++ {
			if q.color[v] == WHITE && gs.sits[u][v]-gs.flow[u][v] > 0 {
				q.add(v)
				gs.pred[v] = u
			}
		}
	}

	return q.color[target] == RED
}

func min(input1 int, input2 int) int  {
	if input1 < input2 {
		return input1
	}else{
		return input2
	}
}

func (gs *fordScheduler) maxFlow() int {
	var maxflow int = 0
	var travelCount = make([]int, 0)

	// used to calc number of days spent
	indexFlowWithA := make ([]AnalysedFlux, 0)
	indexFlow := 0
	
	for gs.bfs(gs.O, gs.D) {
		// increment is the number of Atletas that can be transported on the way
		increment := MaxSize
		for u := gs.airportsV - 1; gs.pred[u] >= 0; u = gs.pred[u] {
			increment = min(increment, gs.sits[gs.pred[u]][u]-gs.flow[gs.pred[u]][u])
		}

		// Flow is the path will be filled by Atletas
		aux := 1
		for u := gs.airportsV - 1; gs.pred[u] >= 0; u = gs.pred[u] {
			gs.flow[gs.pred[u]][u] += increment
			gs.flow[u][gs.pred[u]] -= increment

			indexFlowWithA[indexFlow].path[aux] = u
			aux++
		}
		
		
		indexFlowWithA[indexFlow].capacity = increment

		travelCount = append(travelCount, increment)
		maxflow += increment
	}

	return maxflow
}

func (gs *fordScheduler) findBiggerTravel(travels QueueTravel) int {
	element := 0
	for _, travel := range travels {
		if travel.tail > element {
			element = travel.tail
		}
		if travel.head > element {
			element = travel.head
		}
	}
	return element
}

func (gs *fordScheduler) startNew(OInput int, DInput int, edges QueueTravel) {
	index := gs.findBiggerTravel(edges) + 1
	gs.airportsV = index

	gs.sits = make([][]int, index)
	gs.flow = make([][]int, index)

	for i := range gs.sits { // dos not make difference use sits or flow (they have same size)
		gs.flow[i] = make([]int, index)
		gs.sits[i] = make([]int, index)
	}

	gs.O = OInput
	gs.D = DInput

	gs.pred = make([]int, index)

	for _, edge := range edges {
		gs.sits[edge.tail][edge.head] = edge.capacity
	}
}

runner.go

package main

import "fmt"


func readEntry() (int, int, int) {
	var N, M , A int

	fmt.Scanf("%d %d %d", &N, &M, &A)

	if N == M && M == A && A == 0 {
		// end of test cases
		return 0, 0, 0
	}

	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)

	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 fordFulkersonAlgotithm(O int, D int, A QueueTravel) int{
	var funcCaller = &fordScheduler{}
	funcCaller.startNew(O, D, A)
	return funcCaller.maxFlow()
}
func main() {
	for{
		fmt.Println("enter with 3 numbers N M A")
		N, M, A := readEntry()
		if N == M && M == A && A == 0{
			return
		}
		if N == M && M == A && A == 0 {
			return
		}

		var i int
		var tr = QueueTravel{}

		for i = 0; i < M; i++ {
			A, B, C := readEntryLine(N)
			tr = append(tr,Travel{tail: A, head: B, capacity: C})
		}
		// max flow

		fmt.Println("bfs, mey return a list with path that ")

		// here we calculate Ford Fulkerson
		ret := fordFulkersonAlgotithm(1, N, tr)
		fmt.Println("%d", ret)
	}
}