【テンプレート】ネットワーク最大ストリームEdmonds-Karpアルゴリズム

//
//  main.cpp
//  EK
//
//  Created by MaKai on 2017/3/19.
//  Copyright © 2017  MaKai. All rights reserved.
//

#include 
#include 
#include 
using namespace std;

//Suppose there are only 10 vertexes at most
const int MAX_VERTEX = 10;
const int MAX_VALUE = 0x7FFFFFFF;

int graph[MAX_VERTEX][MAX_VERTEX];

int vertex_number;
queue fifo_queue;
//store current vertex's prefix vertex
int prefix[MAX_VERTEX];
//store stream size of path which start s and end with current node
int stream[MAX_VERTEX];

/**
 * v0-s
 * v1-v1
 * v2-v2
 * v3-t
 */
void BuildGraph() {
    vertex_number=4;
    for (int i=0; i 0 && prefix[i]==-1) {
                    fifo_queue.push(i);
                    prefix[i] = current;
                    //store current path's stream size
                    stream[i] = min(stream[current], graph[current][i]);
                    if (i == stop) {
                        break;
                    }
                }
            
            //break if we have found target node
            if (stream[stop])
                break;
        }
        
        for (int i = 0; i < vertex_number; i++)
            printf("[path] %d->%d
", prefix[i], i);

        if (stream[stop]) {
            int max_value = stream[stop];
            max_stream += max_value;
            //modify graph stream value
            for (int current=stop; current!=start; current = prefix[current]) {
                printf("%d->%d, current stream is %d, will use %d 
", prefix[current], current, graph[prefix[current]][current], max_value);
                graph[prefix[current]][current] -= max_value;
                graph[current][prefix[current]] += max_value;
            }
        } else {
            printf("No available path found, exit now
");
            break;
        }
    }
    printf("Max stream size is:%d
", max_stream);
}

int main(int argc, char** argv) {
    BuildGraph();
    SearchTarget(0, 3);
//    int a = 1 << 30;
//    printf("%d
", a);
    return 0;
}