Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- // Чтение графа происходит из файла in.txt, который устроен следующим образом
- // Сначала идет целое число n - количество вершин
- // Затем идет n строк по n целых чисел в каждой строке - матрица смежности графа
- // Запись осуществляется в файл out.txt
- // Выводит ребра в паросочетании
- unsigned const int MAX_SIZE = 100;
- void read_graph(int * graph, int * n, 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_matching(int * flow, int n, const char * filename);
- void write_flow(int * flow, int n, int max_flow, const char * filename);
- void print_path(int * path, int n);
- int is_two_parts(int * graph, int * parts, 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], parts[MAX_SIZE]; // Матрица смежности графа
- int n, a, b, i, j; // n - количество вершин. Из вершины a в вершину b ищем минимальный путь. max_flow - величина максимального потока
- int * ptr_graph = (int*)graph; // Указатель на матрицу смежности
- int * ptr_flow = (int*)flow; // Указатель на поток
- read_graph(ptr_graph, &n, "in.txt"); // Считываем граф
- if (!is_two_parts(ptr_graph, parts, n)){
- printf("It's not double-parts graph!");
- return 1;
- }
- // Добавляем в наш граф две вершины :
- // Первую вершину (a) соединяем ребрами со всеми вершинами из parts, для которых parts[i] = 0
- // Вторую вершину (b) соединяем ребрами со всеми вершинами из parts, для которых parts[i] = 1
- a = n - 2; b = n - 1; // Добавленные вершины
- // Добавляем соответствующие ребра
- for(i = 0; i < n-2; i++){
- *(ptr_graph+i*n+a) = *(ptr_graph+a*n+i) = parts[i];
- *(ptr_graph+i*n+b) = *(ptr_graph+b*n+i) = 1 - parts[i];
- }
- if (search_flow(ptr_graph, n, a, b, ptr_flow)) // Ищем максимальный поток
- printf("The max matching has been successfully found!\n");
- else
- printf("The max matching does not exist!\n");
- // Удаляем из потока добавленные нами вершины:
- for(i = 0; i < n; i++){
- *(ptr_flow+i*n+a) = *(ptr_flow+a*n+i) = 0;
- *(ptr_flow+i*n+b) = *(ptr_flow+b*n+i) = 0;
- }
- // Записываем максимальное паросочетание из максимального потока в файл:
- write_matching(ptr_flow, n, "out.txt");
- return 0;
- }
- int is_two_parts(int * graph, int * parts, int n){
- // Данная функция проверяет граф на двудольность и разбивает множество его вершин на две доли
- // parts[i] = 0, если точка принадлежит одной доли, иначе 1, если принадлежит другой доли
- int q[MAX_SIZE], q_len = 0, i; // Очередь для обработки вершин
- for(i = 0; i < n; i++)
- parts[i] = -1; // Массив для чередования четности/нечетности вершин обнуляем
- push(q, &q_len, 0); parts[0] = 1; // Кидаем стартовую вершину и говорим, что она нечетная
- // Начинаем обрабатывать вершины
- while (q_len) { // Пока не обработаны все вершины в очереди
- const int t = pop(q, &q_len); // Вынимаем очередную вершину
- for (i = 0; i < n; ++i) { // Обрабатываем все смежные с ней вершины
- if (!*(graph+t*n+i)) continue; // Если нет ребра , то выходим
- if (parts[i] == -1 ){ // Если ее еще никто не посетил
- parts[i] = 1-parts[t]; // Ставим у нее четность , противоположную четности той вершины , откуда пришли
- push(q, &q_len, i); // Ну и кидаем в очередь
- } else if (parts[i] == parts[t])// Если четности двух соседних вершин совпали
- return 0; // То граф не двудольный
- }
- }
- // Наш граф двудольный
- return 1;
- }
- 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; // По одному и тому же ребру в этом случае не ходим
- *(flow+a*n+b) += d; // Прибавляем ее к длине ребра a -> b в нашем потоке
- }
- }
- void read_graph(int * graph, int * n, const char * filename){
- // Открываем файл для чтения:
- FILE *fp;
- fp = fopen(filename, "r");
- // Считываем оттуда количество вершин, вершину a и вершину b:
- fscanf(fp, "%d", n);
- // Считываем оттуда матрицу смежности графа:
- int i, j, k;
- for (i = 0; i < *n; i++){
- for (j = 0; j < *n; j++)
- fscanf(fp, "%d ", graph+(*n+2)*i+j);
- *(graph+(*n+2)*i+j)=0;
- *(graph+(*n+2)*i+j+1)=0;
- }
- for(k = 0; k < 2; k++)
- for(j = 0; j < *n+2; j++)
- *(graph+(*n+2)*(i+k)+j) = 0;
- *n += 2;
- // Закрываем файл
- 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_matching(int * flow, int n, const char * filename){
- // Запись максимального паросочетания в файл. Из записи необходимо исключить вершины a и b, так как они были добавлены нами искусственно для вычисления потока
- FILE *fp;
- fp = fopen(filename, "w");
- int i, j;
- for (i = 0; i < n; i++)
- for (j = i+1; j < n; j++)
- if (*(flow+n*i+j) || *(flow+n*j+i))
- fprintf(fp, "%d %d\n", i, j);
- }
- 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));
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement