Міністерство освіти та науки України Національний університет “Львівська політехніка” Звіт до лабораторної роботи №3 “Теорія транспортних сіток” Львів 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 Висновок: У даній лабораторній роботі я освоїла метод Форда-Фалкерсона для обчислення максимального потоку у транспортній мережі.