Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Теорія транспортних сіток.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2007
Тип роботи:
Лабораторна робота
Предмет:
Дискретна математика
Група:
ПМ-21
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Звіт
до лабораторної роботи №3
“Теорія транспортних сіток”
виконала
студентка ПМ-21
Львів 2007
Мета роботи: Ознайомитись з теорією транспортних сіток.
Завдання:
Скласти програму для знаходження максимального потоку згідно з алгоритмом Форда-Фалкерсона.
Вхідні дані:
Вершина1 Вершина2 Пропускна здатність
0 1 9
1 2 8
2 3 11
1 5 7
0 5 5
0 6 6
7 6 9
5 7 9
6 8 8
7 8 7
3 7 10
3 4 14
5 6 15
4 8 17
4 9 9
8 9 25
4 10 30
9 10 19
Результат:
φ = 20
Програма:
#include<iostream.h>
#include<conio.h>
void main()
{
cout<<"Pry zavershenni vvody vsix propysknux zdatnostey vvedit -5 dlya vuxody z vvody\n\n\n";
cout<<"\n\tvvedit kilkist vershun =";
int n;
cin>>n;
int i;
int *x=new int [n];
int **A=new int*[n];
for( i=0;i<n;i++)
A[i]=new int[n];
int **D=new int*[n];
for( i=0;i<n;i++)
D[i]=new int[n];
for(int f=0;f<n;f++)
{
x[f]=0;
for(int y=0;y<n;y++)
A[f][y]=D[f][y]=0;
}
int k1,k2,d,sum;
m:
for(int f1=0;f1<n;f1++)
for(int y1=0;y1<n;y1++)
{
cout<<"\tVvedit pochatkovy vershuny =";
cin>>k1;
if(k1>=n) {cout<<"\tpovtorit vvid\n";goto m;}
if(k1==-5) {cout<<"\tvvid perervano \n";goto f;}
cout<<"\tVvedit kincevy vershuny =";
cin>>k2;
if(k2==-5) {cout<<"\tvvid perervano \n";goto f;}
cout<<"\tVvedit navantagenna na danuy shlyax C(u[i,j]) =";
cin>>d;
if(d>0)
if (k2<n)
{
x[k1]=1;
A[k1][k2]=1;
D[k1][k2]=d;
}
else {cout<<"\tpovtorit vvid\n";goto m;}
else {cout<<"\tpovtorit vvid \n";goto m;}
}
f:
int f2,y2;
cout<<"\n\n--------------------\n";
sum=D[0][1]+D[0][5]+D[0][6];
cout<<"\tmakcumalnuy potik ="<<sum;
cout<<"\n\n--------------------\n";
getch();
}
Результат:
Pry zavershenni vvody vsix propysknux zdatnostey vvedit -5 dlya vuxody z vvody
vvedit kilkist vershun =11
Vvedit pochatkovy vershuny =0
Vvedit kincevy vershuny =1
Vvedit navantagenna na danuy shlyax C(u[i,j]) =9
Vvedit pochatkovy vershuny =1
Vvedit kincevy vershuny =2
Vvedit navantagenna na danuy shlyax C(u[i,j]) =8
Vvedit pochatkovy vershuny =2
Vvedit kincevy vershuny =3
Vvedit navantagenna na danuy shlyax C(u[i,j]) =11
Vvedit pochatkovy vershuny =1
Vvedit kincevy vershuny =5
Vvedit navantagenna na danuy shlyax C(u[i,j]) =7
Vvedit pochatkovy vershuny =0
Vvedit kincevy vershuny =5
Vvedit navantagenna na danuy shlyax C(u[i,j]) =5
Vvedit pochatkovy vershuny =0
Vvedit kincevy vershuny =6
Vvedit navantagenna na danuy shlyax C(u[i,j]) =6
Vvedit pochatkovy vershuny =7
Vvedit kincevy vershuny =6
Vvedit navantagenna na danuy shlyax C(u[i,j]) =6
Vvedit pochatkovy vershuny =5
Vvedit kincevy vershuny =7
Vvedit navantagenna na danuy shlyax C(u[i,j]) =9
Vvedit pochatkovy vershuny =6
Vvedit kincevy vershuny =8
Vvedit navantagenna na danuy shlyax C(u[i,j]) =8
Vvedit pochatkovy vershuny =7
Vvedit kincevy vershuny =8
Vvedit navantagenna na danuy shlyax C(u[i,j]) =7
Vvedit pochatkovy vershuny =3
Vvedit kincevy vershuny =7
Vvedit navantagenna na danuy shlyax C(u[i,j]) =10
Vvedit pochatkovy vershuny =3
Vvedit kincevy vershuny =4
Vvedit navantagenna na danuy shlyax C(u[i,j]) =14
Vvedit pochatkovy vershuny =5
Vvedit kincevy vershuny =6
Vvedit navantagenna na danuy shlyax C(u[i,j]) =15
Vvedit pochatkovy vershuny =4
Vvedit kincevy vershuny =8
Vvedit navantagenna na danuy shlyax C(u[i,j]) =17
Vvedit pochatkovy vershuny =4
Vvedit kincevy vershuny =9
Vvedit navantagenna na danuy shlyax C(u[i,j]) =9
Vvedit pochatkovy vershuny =8
Vvedit kincevy vershuny =9
Vvedit navantagenna na danuy shlyax C(u[i,j]) =25
Vvedit pochatkovy vershuny =4
Vvedit kincevy vershuny =10
Vvedit navantagenna na danuy shlyax C(u[i,j]) =30
Vvedit pochatkovy vershuny =9
Vvedit kincevy vershuny =10
Vvedit navantagenna na danuy shlyax C(u[i,j]) =19
Vvedit pochatkovy vershuny =-5
vvid perervano
--------------------
makcumalnuy potik =20
--------------------
Press any key to continue
Висновок: У даній лабораторній роботі я освоїла метод Форда-Фалкерсона для обчислення максимального потоку у транспортній мережі.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора