[顯示] [隱藏]

#include "stdafx.h"
#include "iostream"
using namespace std;
//源點為A 終點為F
//印出最大流量和拓樸每個邊之最大流量
struct edge_t {
    char *e;    int   w;
} edges[] = {     
{“AB”, 6}, {“AC”, 8}, {“BD”, 6}, {“BE”, 3},   
{“CD”, 3}, {“CE”, 3}, {“DF”, 8}, {“EF”, 6}  
};
#define E_MAX 8/* 邊線數目 */
#define V_MAX 6                                     /* 節點數目 */
#define index(v) (v-'A') /* Vertex hash function */
#define MIN(x, y) ((x<y)?x:y)  // returns minimum of x and y
enum {
    WHITE = 0,
    GRAY,
    BLACK
};
int capacity[V_MAX][V_MAX]; // capacity matrix
int flow[V_MAX][V_MAX];     // flow matrix
int color[V_MAX]; // needed for breadth-first search               
int pred[V_MAX];  // array to store augmenting path
struct queue {
    int head;    int tail;    int array[V_MAX+2];
} q;
void init_queue() {    q.head = q.tail = 0;  }
void enqueue (int x)  {    q.array[q.tail++] = x;  }
int dequeue (void) {    return q.array[q.head++];  }
int bfs (int start, int target) {
    int x, y;
    for (x=0; x<V_MAX; x++) color[x] = WHITE;
    init_queue();
    enqueue(start);
    color[start] = GRAY;
    pred[start] = -1;
    while (q.head!=q.tail) {
        x = dequeue();
        color[x] = BLACK;
        for (y=0; y<V_MAX; y++) {
            if (color[y]==WHITE && (capacity[x][y]-flow[x][y])>0) {
                enqueue(y);
                color[y] = GRAY;
                pred[y] = x;
            }
        }
    }
    return color[target]==BLACK;
}
void init_network() {
    int i, j;
    // initialize empty capacity matrix
    for (i=0; i<V_MAX; i++) {
        for (j=0; j<V_MAX; j++) {
            capacity[j] = flow[j] = 0;
        }
    }
    // read edge capacities
    for (i=0; i<E_MAX; i++) {
        capacity[index(edges.e[0])][index(edges.e[1])] = edges.w;
    }
}
int edmonds_karp (int source, int sink) {
    int x;
    int increment = 9999;
    int max_flow = 0 [ 瀏覽完整內容請先註冊或登入會員。]