tp2 grafos, professor Cléber

main.go

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 {
	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
	}
	return input2
}

func (gs *fordScheduler) maxFlow() []analysedFlux {
	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 := 0
		pathProvider := make([]int, 0)
		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
			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)
		maxflow += increment
		indexFlow++
	}

	return indexFlowWithA
}

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
	}
}


func readEntry() (int, int, int) {
	var n, m, a int
	_, _ = fmt.Scanf("%d %d %d", &n, &m, &a)

	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) []analysedFlux {
	var funcCaller = &fordScheduler{}
	funcCaller.startNew(o, d, a)
	return funcCaller.maxFlow()
}

func output(input []int){
	// output
	for i:=0; i < len(input); i++{
		fmt.Println(input[i])
	}
}

func main() {
	var daysSpentInTestCase = make([]int, 0)

	for {
		n, m, a := readEntry()
		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)
			tr = append(tr, travel{tail: o, head: d, capacity: s})
		}

		// here we calculate Ford Fulkerson
		flux := fordFulkersonAlgotithm(1, n, tr)

		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)
	}
}