Created
November 17, 2019 16:21
-
-
Save MarceloRosendo/26bb3915ab9984d4716fbbe57cbee563 to your computer and use it in GitHub Desktop.
tp2 grafos, professor Cléber
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 { | |
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