Міністерство освіти та науки України Національний університет “Львівська політехніка” Інститут прикладної математики і фундаментальних наук Кафедра прикладної математики Лабораторна робота № 3 Знаходження максимального потоку в транспортній мережі Львів 2007 Умова задачі: 5.6. Знайти потік найбільшої величини для транспортної сітки: 01 12 23 15 05 06 76 57 68 78 37 34 56 48 49 89 4z 9z  7 10 15 4 10 11 17 18 21 23 19 14 15 17 10 19 19 25   Текст програми: #include <conio.h> #include <stdio.h> #include <iostream.h> //----------------------CONSTANTS AND VARIABLES------------ const kilver=11; //kilkist vershyn int x0=0; //pochatkova vershyna int z=10; //kinceva vershyna int c[kilver][kilver]={ //matrycya propusknyh spromognostey V-25 {0, 7, 0, 0, 0,10,11, 0, 0, 0, 0}, {0, 0,10, 0, 0, 4, 0, 0, 0, 0, 0}, {0, 0, 0,15, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0,14, 0, 0,19, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0,17,10,19}, {0, 0, 0, 0, 0, 0,15,18, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0,21, 0, 0}, {0, 0, 0, 0, 0, 0,17, 0,23, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0,19, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0,25}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} }; struct tochka { int nomer; int vidmichena; int znak; }; int pomicheni[kilver]; //masyp pomichenyh vershyn int f[kilver][kilver]; //matrycya potokiv po rebrah int potic; //max potik cherez meregu tochka path[kilver]; //masyv v jakomu vidobragaetsja shljah int pathlen; //dovgyna vybranogo shlyahu //----------------------FUNCTION PROTOTYPES---------------- void initialization(void); void pershyj_etap(void); void drugyj_etap(void); void vyvid(void); //void findpath(void); int min(tochka *path, int pathlen); //----------------------MAIN------------------------------- void main(void) {clrscr(); initialization(); pershyj_etap(); drugyj_etap(); vyvid(); getch();} //----------------------FUNCTION BODIES-------------------- void initialization(void) {potic=0; pathlen=0; for(int i=0; i<kilver; i++) { for(int j; j<kilver; j++) {f[i][j]=0;}; path[i].nomer=-1; pomicheni[i]=-1; } path[0].nomer=0;} //---------------------- void pershyj_etap(void) {int i; for (i=0;i<kilver;i++){path[i].znak=0;path[i].vidmichena=0;}; int pr=1; //praporec, vidpovidae za isnuvannya shljahu int minchyslo; for(;pr==1;) { for(int u=0;u<kilver;u++){path[u].nomer=-1;}; path[0].nomer=0; pathlen=0; i=0; for(;path[pathlen].nomer!=z;)//znahogennya shlyahu { for(int j=0;j<kilver;j++) //vybyraem nastupnu (sumignu) { pr=0; //shlyah ne isnue if(c[path[pathlen].nomer][j]-f[path[pathlen].nomer][j]>0) {//perevirka chy sumigne i chy propuskae she shos path[pathlen+1].nomer=j;/*path[j].vidmichena=1;break;*/ pathlen++; pr=1; //shlyah isnue i=path[pathlen].nomer; break; } } if(pr==0){break;}; }//for i if(pr==1) { minchyslo = min(path,pathlen); potic+=minchyslo; for(int i=0;i<pathlen;i++) { f[path[i].nomer][path[i+1].nomer]+=minchyslo; } pathlen=0; } }//for pr==1 } //---------------------- int min(tochka *path, int pathlen) {int ret=c[0][path[1].nomer]-f[0][path[1].nomer]; for(int i=1;i<pathlen+1;i++) { if((path[i+1].znak==1)+(path[i+1].vidmichena==0)==1) { if(c[path[i].nomer][path[i+1].nomer]-f[path[i].nomer][path[i+1].nomer]<ret) {ret=c[path[i].nomer][path[i+1].nomer]-f[path[i].nomer][path[i+1].nomer];}; } if(path[i+1].znak==-1) { if(f[path[i].nomer][path[i+1].nomer]<ret) {ret=f[path[i+1].nomer][path[i].nomer];}; } } return ret;} //---------------------- void drugyj_etap(void) {int i; for (i=0;i<kilver;i++){path[i].znak=0;path[i].vidmichena=-1;}; int pr=1; //praporec, vidpovidae za isnuvannya shljahu int minchyslo; int br; for(;pr==1;) { for(int u=0;u<kilver;u++) {path[u].nomer=-1;path[u].vidmichena=-1;path[u].znak=0;pomicheni[u]=-1;}; path[0].nomer=0; path[0].vidmichena=0; pomicheni[0]=1; pathlen=0; i=0; for(;path[pathlen].nomer!=z;)//znahogennya shlyahu { for(int j=kilver-1;j>=0;j--) //vybyraem nastupnu (sumignu) { pr=0; //shlyah ne isnue br=0; if((c[i][j]-f[i][j] >0)*(pomicheni[j]<0)==1) {//perevirka chy sumigne i chy propuskae she shos path[pathlen+1].vidmichena=path[pathlen].nomer; path[pathlen+1].znak=1; path[pathlen+1].nomer=j;/*path[j].vidmichena=1;break;*/ pomicheni[j]=1; pathlen++; pr=1; //shlyah isnue i=path[pathlen].nomer; br=1; } if((f[j][i]>0)*(pomicheni[j]<0)==1) { path[pathlen+1].vidmichena=path[pathlen].nomer; path[pathlen+1].znak=-1; path[pathlen+1].nomer=j;/*path[j].vidmichena=1;break;*/ pomicheni[j]=1; pathlen++; pr=1; //shlyah isnue i=path[pathlen].nomer; br=1; } if(br==1){break;}; } if(pr==0){break;}; }//for i if(pr==1) { minchyslo = min(path,pathlen); potic+=minchyslo; for(int i=0;i<pathlen;i++) { if(path[i+1].znak==1) { f[path[i].nomer][path[i+1].nomer]+=minchyslo; } if(path[i+1].znak==-1) { f[path[i+1].nomer][path[i].nomer]-=minchyslo; } } pathlen=0; } }//for pr==1 } //---------------------- void vyvid(void) {cout<<"\nMaksymalnyj potic cherez transportnu meregu F = "<<potic;} Результат виконання:
Висновок: На лабораторній роботі я навчився реалізовувати алгоритм Форда-Фалкерсона знаходження максимального потоку в транспортній мережі.