Created
November 17, 2019 11:09
-
-
Save MarceloRosendo/bea531a0132e11fcb1cb4985ce24986e 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 { | |
O int | |
D int | |
S 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() | |
// Search all adjacent white nodes v. If the capacity from | |
// u to v in the residual network is positive, enqueue v. | |
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() int { | |
var maxflow int = 0 | |
// While there exists an augmenting path, | |
// increment the flow along this path | |
for gs.bfs(gs.O, gs.D) { | |
// Determine the amount by which we can increment the flow. | |
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]) | |
} | |
// Now increment the flow | |
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 | |
} | |
maxflow += increment | |
} | |
return maxflow | |
} | |
func (gs *fordScheduler) findBiggerTravel(travels QueueTravel) int { | |
element := 0 | |
for _, travel := range travels { | |
if travel.O > element { | |
element = travel.D | |
} | |
if travel.D > element { | |
element = travel.D | |
} | |
} | |
return element | |
} | |
func (gs *fordScheduler) startNew(OInput int, DInput int, edges QueueTravel) { | |
index := gs.findBiggerTravel(edges) | |
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.D][edge.O] = edge.S | |
} | |
} |
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) int{ | |
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{O: A, D: B, S: 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