Бывалый
Профиль
Группа: Участник
Сообщений: 184
Регистрация: 6.6.2006
Где: Россия
Репутация: нет
Всего: нет
|
hi! раскопал консолевскую прогу на с++ и перевёл на делфи но чтото не так при некоторых исходных данных работает неправильно а при некоторых вылетает с ошибкой в памяти тут уже введены исходные данные кто поможет нати вчём дело а то запарился уже двое суток искал ошибку никак не пойму в чём дело | Код |
-----------------------------------------------------
#include <iostream.h>
#include <stdlib.h> //Для функции abs().
#define TRUE 1
#define FALSE 0
#define MaxNodes 7 //Количество вершин.
#define MaxInt 1000 //Машинный эквивалент бесконечности.
//Описание типа узла.
struct Uzel
{
int Element; //Заданный номер вершины.
int Propusk; //Пропускная способность.
int Metka; //Помечена вершина или нет.
};
class Spisok
{
private:
int C[MaxNodes][MaxNodes]; //Матрица начальных пропускных способностей.
int c[MaxNodes][MaxNodes]; //Матрица конечных пропускных способностей.
int Put[MaxNodes][MaxNodes]; //Матрица сквозных путей.
int Potok [MaxNodes]; //Потоки.
int Est (Uzel*,int,int);
int Tpk (int*,int,int);
public:
void Vvod_Ves();
int Reshenie ();
void Vyvod(int);
};
void main()
{
Spisok A;
A.Vvod_Ves();
A.Vyvod(A.Reshenie());
int conec;
cin >> conec;
}
void Spisok::Vvod_Ves()
//Ввод матрицы пропускных способностей.
{
/*cout << "Вводите пропускные способности ребер:\n";
for (int i=0;i<MaxNodes;i++){
for (int j=0;j<MaxNodes;j++)
{
cout << "Введите C[" << (i+1) << "," << (j+1) << "]: ";
cin >> C[i][j];
c[i][j] = C[i][j];
*/
c[0][0] = C[0][0]=0;
c[0][1] = C[0][1]=10;
c[0][2] = C[0][2]=10;
c[0][3] = C[0][3]=10;
c[0][4] = C[0][4]=0;
c[0][5] = C[0][5]=0;
c[0][6] = C[0][6]=0;
c[1][0] = C[1][0]=0;
c[1][1] = C[1][1]=0;
c[1][2] = C[1][2]=0;
c[1][3] = C[1][3]=0;
c[1][4] = C[1][4]=9;
c[1][5] = C[1][5]=0;
c[1][6] = C[1][6]=8;
c[2][0] = C[2][0]=0;
c[2][1] = C[2][1]=0;
c[2][2] = C[2][2]=0;
c[2][3] = C[2][3]=0;
c[2][4] = C[2][4]=8;
c[2][5] = C[2][5]=3;
c[2][6] = C[2][6]=0;
c[3][0] = C[3][0]=0;
c[3][1] = C[3][1]=0;
c[3][2] = C[3][2]=4;
c[3][3] = C[3][3]=0;
c[3][4] = C[3][4]=0;
c[3][5] = C[3][5]=3;
c[3][6] = C[3][6]=0;
c[4][0] = C[4][0]=0;
c[4][1] = C[4][1]=0;
c[4][2] = C[4][2]=0;
c[4][3] = C[4][3]=0;
c[4][4] = C[4][4]=0;
c[4][5] = C[4][5]=0;
c[4][6] = C[4][6]=10;
c[5][0] = C[5][0]=0;
c[5][1] = C[5][1]=0;
c[5][2] = C[5][2]=0;
c[5][3] = C[5][3]=0;
c[5][4] = C[5][4]=0;
c[5][5] = C[5][5]=0;
c[5][6] = C[5][6]=8;
c[6][0] = C[6][0]=0;
c[6][1] = C[6][1]=0;
c[6][2] = C[6][2]=0;
c[6][3] = C[6][3]=0;
c[6][4] = C[6][4]=0;
c[6][5] = C[6][5]=0;
c[6][6] = C[6][6]=0;
// } cout << endl;}
}
void Spisok::Vyvod(int n)
//Вывод результатов.
{
//Вычисление максимального объема потока.
for (int i=0,sum=0;i<=n;sum+=Potok[i++]);
cout << "\nМаксимальный объем потока в сети: " << sum;
cout << "\nЗначения потоков по различным ребрам:\n";
for (i=0;i<MaxNodes;i++)
for (int j=i;j<MaxNodes;j++)
if (C[i][j])
{
cout << "Ребро (" << (i+1) << "," << (j+1) <<"): ";
cout << "(" << C[i][j] << "," << C[j][i] << ")-(";
cout << c[i][j] << "," << c[j][i] << ")=(";
cout << (C[i][j]-c[i][j]) << "," << (C[j][i]-c[j][i]) << ") ";
cout << "Поток: " << abs(C[i][j]-c[i][j]) << " ";
if (C[i][j]-c[i][j]!=0)
{
cout << "Направление: ";
if (C[i][j]-c[i][j]>0)
cout << (i+1) << "->" << (j+1);
else
cout << (j+1) << "->" << (i+1);
}
cout << endl;
}
}
int Spisok::Reshenie()
{
Uzel SS[MaxNodes]; //Множество узлов, в которые можно перейти.
Uzel S[MaxNodes]; //Путь.
int i,j=0,k,el,mx,mn;
int m; //Текущее количество вершин в пути.
int nomer=-1; //Текущее количество сквозных потоков.
int Tupik[MaxNodes]; //Перечень "тупиковых" вершин.
int N_Tupik; //Количество элементов в массиве.
while (j!=-1)
{
i=m=0;
S[i].Element=0;
S[i].Propusk=MaxInt;
S[i].Metka=TRUE;
el=0;
N_Tupik=-1;
while (el!=MaxNodes-1)
{
j=-1;
for (k=0;k<MaxNodes;k++)
if (c[i][k]!=0) //Если есть ненулевой поток...
if (i>0) //и в путь уже включены вершины...
{
if (!Est(&S[0],m,k) && !Tpk(&Tupik[0],N_Tupik,k))
//то включаем текущую вершину,
//если ее нет в пути и если она не "тупиковая".
{
SS[++j].Element=k;
SS[j].Propusk=c[i][k];
SS[j].Metka=FALSE;
}
}
else
if (!Tpk(&Tupik[0],N_Tupik,k)) //Не вернулись ли назад?
//Поток не нулевой, и это первая вершина.
{ //Включаем эту вершину в путь.
SS[++j].Element=k;
SS[j].Propusk=c[i][k];
SS[j].Metka=FALSE;
}
if (j!=-1) //Есть продолжение.
{
mx=SS[0].Propusk;
el=0;
for (k=1;k<=j;k++)
if (SS[k].Propusk>mx)
{ el=k; mx=SS[k].Propusk; }
S[++m].Element=SS[el].Element;
S[m].Propusk=mx;
S[m].Metka=TRUE;
if (SS[el].Element==MaxNodes-1) //Найден сквозной путь.
{
nomer++;
//Запоминаем сквозной путь.
for (k=0;k<=m;k++)
Put[nomer][k]=S[k].Element;
//Ищем минимальный поток.
mn=S[0].Propusk;
el=0;
for (k=1;k<=m;k++)
if (S[k].Propusk<mn)
{ el=k; mn=S[k].Propusk; }
Potok[nomer]=mn; //Запоминаем его.
//Вычисляем остаточные пропускные способности.
for (k=0;k<m;k++)
{
c[S[k].Element][S[k+1].Element] -= Potok[nomer];
c[S[k+1].Element][S[k].Element] += Potok[nomer];
}
el=MaxNodes-1; //Переход к следующей итерации.
j=0;
}
else i=S[m].Element;
}
else //Продолжения нет. Это возможно тогда, когда:
{
if (i==0) //а) все пропускные способности нулевые.
// В этом случае - выход
el=MaxNodes-1;
else //б) мы попали в тупик. Запомним тупиковую вершину
// в массиве и отступим назад на одну вершину.
{
Tupik[++N_Tupik]=S[m].Element;
m--;
i=S[m].Element;
}
}
}
}
return nomer; //Возвращает количество сквозных потоков.
}
int Spisok::Est(Uzel S[], int m, int k)
//Функция проверяет, есть ли вершина k в пути S.
//m - текущее количество элементов в пути.
//Возвращает 1, если вершина есть, и 0 - в противном случае.
{
for (int l=0;l<=m;l++)
if (S[l].Element==k) return 1;
return 0;
}
int Spisok::Tpk(int Tupik[],int N_Tupik, int k)
//Функция проверяет, есть ли вершина k в массиве "тупиковых" вершин.
//N_Tupik - текущее количество вершин в массиве.
//Возвращает 1, если вершина есть, и 0 - в противном случае.
{
if (N_Tupik==-1) return 0;
for (int l=0;l<=N_Tupik;l++)
if (Tupik[l]==k) return 1;
return 0;
}
-----------------------------------------------------
На делфе
-----------------------------------------------------
unit Unit2;
interface
uses Dialogs,SysUtils;
const MaxNodes=6;
MaxInt=1000;
type
//Описание типа узла.
Uzel = record
Element, //Заданный номер вершины.
Propusk:integer; //Пропускная способность.
Metka:boolean; //Помечена вершина или нет.
end;
Spisok=class
private
CN :array [0..MaxNodes,0..MaxNodes]of integer ; //Матрица начальных пропускных способностей.
cc :array [0..MaxNodes,0..MaxNodes]of integer; //Матрица конечных пропускных способностей.
Put :array [0..MaxNodes,0..MaxNodes]of integer; //Матрица сквозных путей.
Potok :array [0..MaxNodes]of integer; //Потоки.
function Est (S:array of uzel; m:integer;k:integer):boolean;
function Tpk (Tupik:array of integer;N_Tupik:integer;k:integer):boolean;
public
function Vvod_Ves(i,j,ves:integer):boolean;
procedure vesa;
function Reshenie ():integer;
function Vyvod(n:integer):string;
constructor Create;
destructor Destroy; override;
end;
var A:spisok;
implementation
uses unit1;
//создать
constructor Spisok.create;
begin
inherited create;
end;
//удалить
destructor Spisok.Destroy;
begin
//A.Destroy;
inherited destroy;
end;
procedure Spisok.Vesa;
var i,j:integer;
begin
{for i:=0 to MaxNodes do
for j:=0 to MaxNodes do
begin
CN[i,j]:=0;
cc[i,j]:=0;
end; }
cn[0,0]:=0;
cn[0,1]:=10;
cn[0,2]:=10;
cn[0,3]:=10;
cn[0,4]:=0;
cn[0,5]:=0;
cn[0,6]:=0;
cn[1,0]:=0;
cn[1,1]:=0;
cn[1,2]:=0;
cn[1,3]:=0;
cn[1,4]:=9;
cn[1,5]:=0;
cn[1,6]:=8;
cn[2,0]:=0;
cn[2,1]:=0;
cn[2,2]:=0;
cn[2,3]:=0;
cn[2,4]:=8;
cn[2,5]:=3;
cn[2,6]:=0;
cn[3,0]:=0;
cn[3,1]:=0;
cn[3,2]:=4;
cn[3,3]:=0;
cn[3,4]:=0;
cn[3,5]:=3;
cn[3,6]:=0;
cn[4,0]:=0;
cn[4,1]:=0;
cn[4,2]:=0;
cn[4,3]:=0;
cn[4,4]:=0;
cn[4,5]:=0;
cn[4,6]:=10;
cn[5,0]:=0;
cn[5,1]:=0;
cn[5,2]:=0;
cn[5,3]:=0;
cn[5,4]:=0;
cn[5,5]:=0;
cn[5,6]:=8;
cn[6,0]:=0;
cn[6,1]:=0;
cn[6,2]:=0;
cn[6,3]:=0;
cn[6,4]:=0;
cn[6,5]:=0;
cn[6,6]:=0;
cc[0,0] := cn[0,0];
cc[0,1] := cn[0,1];
cc[0,2] := cn[0,2];
cc[0,3] := cn[0,3];
cc[0,4] := cn[0,4];
cc[0,5] := cn[0,5];
cc[0,6] := cn[0,6];
cc[1,0] := cn[1,0];
cc[1,1] := cn[1,1];
cc[1,2] := cn[1,2];
cc[1,3] := cn[1,3];
cc[1,4] := cn[1,4];
cc[1,5] := cn[1,5];
cc[1,6] := cn[1,6];
cc[2,0] := cn[2,0];
cc[2,1] := cn[2,1];
cc[2,2] := cn[2,2];
cc[2,3] := cn[2,3];
cc[2,4] := cn[2,4];
cc[2,5] := cn[2,5];
cc[2,6] := cn[2,6];
cc[3,0] := cn[3,0];
cc[3,1] := cn[3,1];
cc[3,2] := cn[3,2];
cc[3,3] := cn[3,3];
cc[3,4] := cn[3,4];
cc[3,5] := cn[3,5];
cc[3,6] := cn[3,6];
cc[4,0] := cn[4,0];
cc[4,1] := cn[4,1];
cc[4,2] := cn[4,2];
cc[4,3] := cn[4,3];
cc[4,4] := cn[4,4];
cc[4,5] := cn[4,5];
cc[4,6] := cn[4,6];
cc[5,0] := cn[5,0];
cc[5,1] := cn[5,1];
cc[5,2] := cn[5,2];
cc[5,3] := cn[5,3];
cc[5,4] := cn[5,4];
cc[5,5] := cn[5,5];
cc[5,6] := cn[5,6];
cc[6,0] := cn[6,0];
cc[6,1] := cn[6,1];
cc[6,2] := cn[6,2];
cc[6,3] := cn[6,3];
cc[6,4] := cn[6,4];
cc[6,5] := cn[6,5];
cc[6,6] := cn[6,6];
end;
function Spisok.Vvod_Ves(i,j,ves:integer):boolean;
begin
CN[i,j]:=ves;
cc[i,j]:=ves;
form1.memo1.lines.add('['+inttostr(i)+'] ['+inttostr(j)+'] ='+inttostr(ves));
end;
function Spisok.Vyvod(n:integer):string;
//Вывод результатов.
var i,j,sum:integer;
begin
//Вычисление максимального объема потока.
sum:=0;
for i:=0 to n do
sum:=sum+Potok[i];
result:=inttostr(sum);
form1.memo1.lines.add('Максимальный объем потока в сети: '+result);
{form1.memo1.lines.add('Значения потоков по различным ребрам:');
for i:=0 to MaxNodes do
for j:=i to MaxNodes do
if (CN[i,j]>0)
then begin
form1.memo1.lines.add('Ребро ('+inttostr(i+1)+','+inttostr(j+1)+'): '+
'('+inttostr(CN[i,j])+','+inttostr(CN[j,i])+')-('+
inttostr(cc[i,j])+','+inttostr(cc[j,i])+')=('+
inttostr(CN[i,j]-cc[i,j])+','+inttostr(CN[j,i]-cc[j,i])+') ');
form1.memo1.lines.add('Поток: '+inttostr(abs(CN[i,j]-cc[i,j]))+' ');
if (CN[i,j]-cc[i,j])<>0 then
begin
form1.memo1.lines.add('Направление: ');
if (CN[i,j]-cc[i,j]>0) then
form1.memo1.lines.add(inttostr(i+1)+'->'+inttostr(j+1))
else
form1.memo1.lines.add(inttostr(j+1)+'->'+inttostr(i+1));
end;
end; }
end;
function Spisok.Reshenie():integer;
var
SS:array[0..MaxNodes]of uzel; //Множество узлов, в которые можно перейти.
S:array[0..MaxNodes] of uzel; //Путь.
i,j,k,el,mx,mn:integer;
m:integer; //Текущее количество вершин в пути.
nomer:integer; //Текущее количество сквозных потоков.
Tupik:array[0..MaxNodes] of integer; //Перечень "тупиковых" вершин.
N_Tupik:integer; //Количество элементов в массиве.
begin
j:=0;
nomer:=-1;
while (j<>-1)
do begin
m:=0;
i:=0;
S[i].Element:=0;
S[i].Propusk:=MaxInt;
S[i].Metka:=true;
el:=0;
N_Tupik:=-1;
while (el<>MaxNodes) do
begin
j:=-1;
for k:=0 to MaxNodes do
if (cc[i,k]<>0) then //Если есть ненулевой поток...
if (i>0) then begin //и в путь уже включены вершины...
if ((not Est(S[0],m,k)) and (not Tpk(Tupik[0],N_Tupik,k)))
//то включаем текущую вершину,
//если ее нет в пути и если она не "тупиковая".
then begin
inc(j);
SS[j].Element:=k;
SS[j].Propusk:=cc[i,k];
SS[j].Metka:=FALSE;
end;
end
else
if (not Tpk(Tupik[0],N_Tupik,k)) then//Не вернулись ли назад?
//Поток не нулевой, и это первая вершина.
begin //Включаем эту вершину в путь.
inc(j);
SS[j].Element:=k;
SS[j].Propusk:=cc[i,k];
SS[j].Metka:=FALSE;
end;
if (j<>-1) then//Есть продолжение.
begin
mx:=SS[0].Propusk;
el:=0;
for k:=1 to j do
if (SS[k].Propusk>mx) then
begin
el:=k; mx:=SS[k].Propusk;
end;
inc(m);
S[m].Element:=SS[el].Element;
S[m].Propusk:=mx;
S[m].Metka:=TRUE;
if (SS[el].Element=MaxNodes) then //Найден сквозной путь.
begin
inc(nomer);
//Запоминаем сквозной путь.
for k:=0 to m do
Put[nomer,k]:=S[k].Element;
//Ищем минимальный поток.
mn:=S[0].Propusk;
el:=0;
for k:=1 to m do
if (S[k].Propusk<mn)then
begin
el:=k; mn:=S[k].Propusk;
end;
Potok[nomer]:=mn; //Запоминаем его.
//Вычисляем остаточные пропускные способности.
for k:=0 to m-1 do
begin
dec(cc[S[k].Element,S[k+1].Element], Potok[nomer]);
inc(cc[S[k+1].Element,S[k].Element], Potok[nomer]);
end;
el:=MaxNodes; //Переход к следующей итерации.
j:=0;
end
else i:=S[m].Element;
end
else //Продолжения нет. Это возможно тогда, когда:
begin
if (i=0) then //а) все пропускные способности нулевые.
// В этом случае - выход
el:=MaxNodes
else //б) мы попали в тупик. Запомним тупиковую вершину
// в массиве и отступим назад на одну вершину.
begin
inc(N_Tupik);
Tupik[N_Tupik]:=S[m].Element;
dec(m);
i:=S[m].Element;
end;
end;
end;
end;
result:=nomer; //Возвращает количество сквозных потоков.
end;
function Spisok.Est(S:array of uzel;m:integer;k:integer):boolean;
//Функция проверяет, есть ли вершина k в пути S.
//m - текущее количество элементов в пути.
//Возвращает 1, если вершина есть, и 0 - в противном случае.
var L:integer;
begin
result:=false;
for l:=0 to m do
if (S[l].Element=k) then result:=true;
end;
function Spisok.Tpk(Tupik:array of integer;N_Tupik:integer;k:integer):boolean;
//Функция проверяет, есть ли вершина k в массиве "тупиковых" вершин.
//N_Tupik - текущее количество вершин в массиве.
//Возвращает 1, если вершина есть, и 0 - в противном случае.
var l:integer;
begin
result:=false;
if (N_Tupik=-1) then result:=false;
for l:=0 to N_Tupik do
if (Tupik[l]=k) then result:=true;
end;
begin
A:=Spisok.Create;
end.
-----------------------------------------------------
|
вызывается так A.Vesa(); A.Vyvod(a.Reshenie); help!!! Это сообщение отредактировал(а) Alexeis - 5.6.2007, 20:05 --------------------
Flash ICQ Chuch@"... да как два байта отослать!!!" |
[c++ -> Delphi] Алгоритм нахождения, максимального потока в Графе 
Загрузка ...
potok.rar 67,92 Kb
