Графы. 
Задача китайского почтальона

{.

umin=u[0][j];

for (i=1; i<n; i++) // Минимум в столбце.

umin = umin < u[i][j]? umin: u[i][j];

for (i=0; i<n; i++).

u[i][j]-=umin;

}.

}.

void mark0(int n)// Отмечаем и зачеркиваем нули.

{.

int i, j;

for (i=0; i<n; i++) for (j=0; j<n; j++) cross0[i][j]=0;

for (i=0; i<n; i++) str0[i]=col0[i]=0;

for (i=0; i<n; i++) for (j=0; j<n; j++).

if (i ≠ j && u[i][j]==0).

{.

if (str0[i]==0 && col0[j]==0).

{.

cross0[i][j]=1;

str0[i]=col0[j]=1;

///???

///u[j][i] = inf;

}.

else.

cross0[i][j]=-1;

}.

}.

int findcouple (int i, int n).

{.

int i1, j=0;

while (cross0[i][j]≠1) j++;

for (i1=0; i1<n; i1++).

// Если ноль зачеркнут и в этой строке еще не были.

if (cross0[i1][j]==-1 && !usestr[i1]){.

// Если строка не помечена.

if (!str0[i1]){.

str0[i1]=1;

cross0[i1][j]=1;

cross0[i][j]=-1;

return 1;

}.

else{.

usestr[i1]=1;

if (findcouple (i1,n)){.

cross0[i1][j]=1;

cross0[i][j]=-1;

return 1;

}.

}.

}.

return 0;

}.

// Нахождение паросочетания.

int upcouple (int n).

{.

int i, j;

for (i=0; i<n; i++).

usestr[i]=0; // В какой строке побывали.

for (j=0; j<n; j++).

if (!col0[j]).

for (i=0; i<n; i++).

if (cross0[i][j]==-1){ // Зачеркнутый ноль в непомеченном столбце.

usestr[i]=1;

if (findcouple (i, n)){.

col0[j]=1;

cross0[i][j]=1;

return 1;

}.

else.

usestr[i]=0;

}.

return 0;

}.

// Нахождение максимального паросочетания.

void maxcouple (int n).

{.

while (upcouple (n));

}.

// Проверка на решенность задачи.

bool fin (int n){.

int i;

for (i=0; i<n; i++).

if (!str0[i]).

return false;

return true;

}.

// Нахождение минимальной опоры.

void minsupport (int n).

{.

int i, j, b;

for (i=0; i<n; i++).

strround[i]=colround[i]=0;

for (i=0; i<n; i++).

strround[i]=1-str0[i];

b=1;

while (b){.

b=0;

for (i=0; i<n; i++).

if (strround[i]).

for (j=0; j<n; j++).

if (cross0[i][j]==-1).

colround[j]=1;

for (j=0; j<n; j++).

if (colround[j]).

for (i=0; i<n; i++).

if (cross0[i][j]==1 && !strround[i]){.

b=1;

strround[i]=1;

}.

}.

}.

// Перестановка нулей.

void rotate0(int n).

{.

int i, j, min=vmax;

for (i=0; i<n; i++).

if (strround[i]).

for (j=0; j<n; j++).

if (!colround[j]).

if (min>u[i][j]).

min=u[i][j];

for (i=0; i<n; i++).

if (!strround[i]).

for (j=0; j<n; j++).

u[i][j]+=min;

for (j=0; j<n; j++).

if (!colround[j]).

for (i=0; i<n; i++).

u[i][j]-=min;

}.

void HungarianMethod (int n, bool ToMax=false).

// ToMax == TRUE — задача на максимум,.

// ToMax == FALSE — задача на минимум.

{.

privod (n, ToMax);

while (true).

{.

mark0(n);

maxcouple (n);

if (fin (n)) break;

minsupport (n);

rotate0(n);

}.

//Результат — в cross[i][j], если 1 — то это и есть искомое «назначение» .

}.

void Graph: Step2().

//Найти наибольшее паросочетание M с минимальным весом.

//Используется венгерский алгоритм решения задачи о назначениях.

//паросочетание или независимое множество рёбер в графе — это набор попарно несмежных рёбер.

//Наибольшее паросочетание — это такое паросочетание, которое содержит максимальное количество рёбер

//Венгерский алгоритм находит полное паросочетание минимального веса.

//Паросочетание называется полным, если оно покрывает все вершины графа.

//Алгоритм, решающий задачу, работает с графом, как с матрицей весов.

//Вычитаем из каждой строки значение ее минимального элемента. Теперь в каждой строке есть хотя бы один нулевой элемент.

//Вычитаем из каждого столбца значение его минимального элемента. Теперь в каждом столбце есть хотя бы один нулевой элемент.

//Ищем в текущем графе полное паросочетание из ребер нулевого веса.

//Если оно найдено, то алгоритм закончен.

{.

v = createintmatrix (V);

for (int i=0; i<V; i++).

for (int j=0; j<V; j++).

v[i][j] = D[i][j]; //graph[i][j];

u = createintmatrix (V);

if (cross0) destroyintmatrix (cross0,V);

cross0 = createintmatrix (V);

str0 = new int[V];

col0 = new int[V];

strround = new int[V];

colround = new int[V];

usestr = new int[V];

vmax=0;

HungarianMethod (V);

delete[]usestr;

delete[]colround;

delete[]strround;

delete[]col0;

delete[]str0;

//destroyintmatrix (cross0,V);

destroyintmatrix (u, V);

destroyintmatrix (v, V);

}.

void Graph: Step3().

//Строим граф GM.

//Для каждой пары вершин va и vb.

//Если она паросочетается, то определить цепь наименьшего веса Mu.

//Добавим искусственные рёбра в GM, соответствующие ребрам из Mu.

//При этом будем подсчитывать, сколько раз добавлено искусственное ребро в матрице GC.

//(вес искусственного ребра берётся равным весу параллельного ему реального ребра).

{.

//Нет дополнительных ребер

for (int i=0; i < V; i++).

for (int j=0; j < V; j++).

GC[i][j]=0;

if (isEulerianCycle ()) return; //Ничего делать больше не нужно.

for (int va=0; va < V; va++).

for (int vb=0; vb < V; vb++).

if (cross0[va][vb] ≠ 0) { //Назначено.

int Len=0;

int * path = DijkstraPath (va, vb, Len); //path длиной L — список ребер

for (int i=0; i < Len-1; i++).

{.

int from = path[i];

int to = path[i+1];

GC[from][to]++;

GC[to][from]++;

}.

delete []path;

}.

}.

String Graph: Step4() //Не использован, но может пригодиться.

//Сформировать строку, в которой:

//подсчитывается общая длина пути.

//указываются ребра, по которым придется пройти больше 1 раза.

//Сумма весов всех рёбер графа GM с добавленными ребрами.

//равна минимальному весу цикла проходящего по graph.

//При этом число прохождений цикла по ребру (a, b).

//равно общему числу параллельных ребер (a, b) (исходных и искусственных).

{.

//Посчитать общий вес.

//Для всех ребер из graph.

//Добавить его длину к общей сумме.

//умноженную на количество дополнительных ребер

int Sum = 0;

for (int i=0; i < V; i++).

for (int j=i+1; j < V; j++).

if (graph[i][j] ≠ inf).

Sum+=graph[i][j] * (1 + GC[i][j]);

String Result = «Длина «+IntToStr (Sum);

//Добавленные ребра.

for (int i=0; i < V; i++).

for (int j=i+1; j < V; j++).

if (GC[i][j] > 2).

Result+= ««+IntToStr (i)+» .

-" +IntToStr (j);

return Result;

}.

String Graph: Solve ().

//Решить и вернуть общий вес + путь.

/*.

В случае неэйлерова графа в первую очередь нужно решить следующую подзадачу. В неэйлеровом графе необходимо най;

ти минимальное дополнение графа до эйлерова, где минимальное дополнение графа до эйлерова — это рёбра и числа k повторений каждого ребра, такие, что при дублировании каждого ребра из этого подмножества k раз будет получен граф, в котором все вершины будут сбалансированы, т. е. эйлеров граф. После того, как будет найдено минимально дополнение графа до эйлерова, следует применить алгоритм поиска эйлерова цикла. Таким образом, будет получено решение задачи китайского почтальона.

*/.

{.

Step1();

Step2();

Step3();

return Path ();

}.

int Graph: EdgeCount ().

{.

int Result = 0;

for (int i=0; i < V; i++).

for (int j=0; j < V; j++).

{.

if (graph[i][j] ≠ inf) Result++;

}.

return Result/2;

}.

void Graph: RemoveEdge (int from, int to).

//Удалить указанное ребро.

{.

if (GC[from][to]>0) {.

GC[from][to]-=2;

GC[to][from]-=2;

}.

else.

{.

graph[from][to]=inf; //Окончательно.

graph[to][from]=inf;

}.

}.

int ** Copy=NULL;

String Graph: Path ().

//Получить Эйлеров цикл в графе с учетом дополнительных ребер

/*.

Для решения поставленной задачи используется следующий алгоритм поиска эйлерова цикла в эйлеровом графе.

Вход: неориентированный взвешенный эйлеров граф.

Выход: Цикл, проходящий через каждое ребро графа.

— Выбрать произвольную вершину u. Добавить вершину u в список результата.

— Выбрать произвольное ребро (u, v).

— Отметить ребро (u, v), как пройденное.

— Добавить вершину v в список результата.

— Выбрать произвольное ребро (v, w).

— Повторять пункты 2 — 5 до тех пор, пока все ребра не будут помечены как пройденные.

*/.

{.

int Len = 0;

Copy = createintmatrix (V);

for (int i=0; i < V; i++).

for (int j=0; j < V; j++).

Copy[i][j] = graph[i][j];

const int start = 0;

//Выбрать произвольную вершину u.

int from = start;

int to;

String Result = IntToStr (from+1);

while (true).

{.

//Выбрать произвольное ребро (u, v).

//отдавать предпочтение множественным ребрам!

bool found = false;

for (to=0; to < V; to++).

{.

if (graph[from][to] == inf) continue; //нет ребра вообще.

if (GC[from][to]==0) continue; //есть, но не множественное.

//Найдено нужное ребро.

found = true;

break;

}.

if (!found).

//искать обычное ребро, желательно — «следующее по номеру» .

for (to=0+from+1; to < V+from+1; to++).

{.

int index = to % V;

if (graph[from][index] ≠ inf) {found = true;to = index; break;};

}.

if (!found) break; //ребра кончились.

Len += graph[from][to];

RemoveEdge (from, to);

Result+=" - «;

Result+=IntToStr (to+1);

from = to;

}.

for (int i=0; i < V; i++).

for (int j=0; j < V; j++).

graph[i][j] = Copy[i][j];

destroyintmatrix (Copy, V);

return «Длина «+IntToStr (Len)+» Цикл «+Result;

}.

#pragma package (smart_init).

Модуль Unit1.cpp.

//—————————————————————————————————————;

#include <vcl.h>

#pragma hdrstop.

#include «Unit1.h» .

#include «UnitGraph.h» .

//—————————————————————————————————————;

#pragma package (smart_init).

#pragma resource «*.dfm» .

TForm1 *Form1;

//—————————————————————————————————————;

__fastcall TForm1: TForm1(TComponent* Owner).

: TForm (Owner).

{.

}.

//—————————————————————————————————————;

Graph * G;

void __fastcall TForm1: FormCreate (TObject *Sender).

{.

G = new Graph («Graph.txt»);

}.

//—————————————————————————————————————;

void __fastcall TForm1: PaintBox1Paint (TObject *Sender).

{.

if (G) G->Paint (PaintBox1->Canvas, PaintBox1->Width, PaintBox1->Height);

}.

//—————————————————————————————————————;

void __fastcall TForm1: Button1Click (TObject *Sender).

{.

if (OpenDialog1->Execute ()) {.

delete G;

G = new Graph (OpenDialog1->FileName);

PaintBox1->Repaint ();

LabelPath->Caption = «Путь: не искал» ;

}.

}.

//—————————————————————————————————————;

void __fastcall TForm1: Button2Click (TObject *Sender).

{.

LabelPath->Caption = G->Solve ();

}.

//—————————————————————————————————————;