max_flow

#include <stdio.h>

// Чтение графа происходит из файла in.txt, который устроен следующим образом
// Сначала идут три целых числа: n - количество вершин, a - пункт отправления, b - пункт назначения
// Затем идет n строк по n целых чисел в каждой строке - матрица смежности графа
// Запись осуществляется в файл out.txt
// В первой строчке записывается величина максимального потока
// Затем записывается матрица смежности нашего потока

unsigned const int MAX_SIZE = 100;

void read_graph(int * graph, int * n, int * a, int * b, const char * filename);
int search_path(int * graph, int n, int a, int b, int * path, int * path_len);
int search_flow(int * graph, int n, int a, int b, int * flow);
int search_min(int * graph, int n, int * path, int path_len);
void update_flow(int * graph, int * flow, int n, int d, int * path, int path_len);
void write_flow(int * flow, int n, int max_flow, const char * filename);
void print_path(int * path, int n);

int pop(int * queue, int * n);
void push(int * queue, int * n, int value);

int main(){
    int graph[MAX_SIZE][MAX_SIZE], flow[MAX_SIZE][MAX_SIZE]; // Матрица смежности графа и поток
    int n, a, b, max_flow; // n - количество вершин. Из вершины a в вершину b ищем минимальный путь. max_flow - величина максимального потока

    int * ptr_graph = (int*)graph; // Указатель на матрицу смежности
    int * ptr_flow = (int*)flow; // Указатель на поток

    read_graph(ptr_graph, &n, &a, &b, "in.txt"); // Считываем граф

    if (max_flow = search_flow(ptr_graph, n, a, b, ptr_flow)) // Ищем максимальный поток
        printf("The max flow has been successfully found!\n");
    else
        printf("The max flow does not exist!\n");

//  Записываем максимальный поток и его величину в файл:
    write_flow(ptr_flow, n, max_flow, "out.txt");

    return 0;
}

void print_path(int * path, int n){
//  Вывод пути на экран
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", path[i]);
    printf("\n");
}

int search_flow(int * graph, int n, int a, int b, int * flow){
    int path[MAX_SIZE], path_len = 0, d;

//  Пока мы можем найти какой - либо путь из вершины а в вершину b
    while (search_path(graph, n, a, b, path, &path_len)) {
        d = search_min(graph, n, path, path_len); // Вычисляем минимальную длину ребра на этом пути
        update_flow(graph, flow, n, d, path, path_len); // Обновляем матрицу смежности и матрицу потока на величину d
    }

//  Дальше суммируем длинны всех исходящих из вершины а ребер . Это и будет величина нашего максимального потока
    int max_flow = 0, i;
    for (i = 0; i < n; ++i)
        if (d = *(flow+a*n+i))
            max_flow += d;

//  Возвращаем найденную нами величину максимального потока
    return max_flow;
}

int search_min(int * graph, int n, int * path, int path_len){
//  Данная функция ищет минимальную длину среди длин всех ребер маршрута path
    int i = 0, d, min;
    min = *(graph+path[i]*n+path[i+1]);
    for (i = 1; i < path_len - 1; i++)
        if (min > (d = *(graph+path[i]*n+path[i+1])))
            min = d;
    return min;
}

void update_flow(int * graph, int * flow, int n, int d, int * path, int path_len){
//  Данная функция обновляет ребра маршрута path в матрице смежности graph и матрице потока flow на величину d
    int i;
    for (i = 0; i < path_len - 1; i++){
        int a = path[i], b = path[i+1];
        *(graph+a*n+b) -= d; // Вычитаем из длины ребра a -> b величину d
        *(graph+b*n+a) += d; // Прибавлем ее к длине ребра b -> a
        *(flow+a*n+b) += d; // Прибавляем ее к длине ребра a -> b в нашем потоке
        *(flow+b*n+a) -= d; // Вычитаем ее из длины ребра b -> a в нашем потоке
    }
}

void read_graph(int * graph, int * n, int * a, int * b, const char * filename){
//  Открываем файл для чтения:
    FILE *fp;
    fp = fopen(filename, "r");

//  Считываем оттуда количество вершин, вершину a и вершину b:
    fscanf(fp, "%d %d %d", n, a, b);

//  Считываем оттуда матрицу смежности графа:
    int i, j;
    for (i = 0; i < *n; i++)
        for (j = 0; j < *n; j++)
            fscanf(fp, "%d ", graph+(*n)*i+j);

//  Закрываем файл
    fclose(fp);
}

int pop(int * queue, int * n){
//  Вынимаем элемент из очереди
    int t = queue[0], i;
    *n -= 1;
    for(i = 0; i < *n; i++)
        queue[i] = queue[i+1];
    return t;
}

void push(int * queue, int * n, int value){
//  Кладем новый элемент в очередь
    queue[*n] = value;
    *n += 1;
}

int search_path(int * graph, int n, int a, int b, int * path, int * path_len){
//  Ищем минимальный путь поиском в ширину
    *path_len = 0; // Длина пути

    int visited[MAX_SIZE], q[MAX_SIZE]; // Посещенные вершины и очередь для посещения вершин
    int q_len = 0, i, j; // Длина очереди и счетчики циклов

    for(i = 0; i < n; i++) // Обнуляем массив посещенны вершин
        visited[i] = -1;

//  Кидаем стартовую вершину в очередь и запоминаем, что мы ее посетили:
    push(q, &q_len, a);
    visited[a] = a;

//  Пока мы не обработали необходимые вершины, обрабатываем их:
    while (q_len > 0) {
//      Вынимаем очередную вершину:
        const int t = pop(q, &q_len);
//      Если мы достигли необходимой вершины, то логично бы прекратить поиск
        if (t == b) break;
//      В цикле кидаем в очередь все непосещенные смежные с вершиной t вершины:
        for (i = 0; i < n; i++)
//          ЕСЛИ существтует ребро t -> i и ЕСЛИ мы по нему еще не прошли:
            if (*(graph+t*n+i) && visited[i] == -1 ) {
                visited[i] = t; // Сохраняем в visited[i] вершину t, из которой мы пришли в вершину i
                push(q, &q_len, i); // Кидаем вершину i в очередь обработки
            }
    }

//  Возвращаемся из вершины b в вершину a по тому пути , который мы запомнили в visited
    while ( b != a && visited[b] != -1 ){
        push(path, path_len, b); // Кидаем вершины в вектор пути
        b = visited[b];
    }

//  Если нам удалось дойти до стартовой вершины , то кидаем ее в наш путь
    if ( b == a ) push(path, path_len, a);

//  Приведение пути к нормальному виду (переворачиваем его)
    for (i = 0, j = *path_len-1; i < j; ++i,--j){
        int temp = path[i];
        path[i] = path[j];
        path[j] = temp;
    }

    return *path_len; // Возвращаем длину найденного пути
}

void write_flow(int * flow, int n, int max_flow, const char * filename){
//  Запись потока в файл
    FILE *fp;
    fp = fopen(filename, "w");
    int i, j;
    fprintf(fp, "%d\n", max_flow);
    for (i = 0; i < n; i++, fprintf(fp, "\n"))
        for(j = 0; j < n; j++)
            fprintf(fp, "%d ", *(flow+i*n+j));
}