Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Graphs tp2 final https://br.spoj.com/problems/OLIMP/ Adriana Daniel Higor Henrique Marcelo
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)
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
You can’t perform that action at this time.