Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
tp2 grafos, professor Cléber
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)
}
}
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.