Created
November 17, 2019 13:28
-
-
Save MarceloRosendo/46db46f05af5aaccdaa3d0b0d7a985d9 to your computer and use it in GitHub Desktop.
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 | |
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 | |
} |
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 | |
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() []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 | |
} | |
} |
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" | |
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) []AnalysedFlux{ | |
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) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment