PDA

View Full Version : Thuật toán Ford - Fulkerson...Code đã chạy mà khi ra kết quả thì ra số 0 . Ai biết chỉ dùm với..



ngocvientk91
29-09-2011, 08:30 PM
#include <conio.h>
#include <stdio.h>
#define max 1000
int A[max][max];
int f[max][max];//Flow on edges
int p[max], e[max];
int Q[max];//Quene
int n, s, t;//Number of vertex, the source, the sink
int fr=0, r=0;//Front, Rear of Quene
int initNetwork(){
//initialize network with zero flow
int i, j;
printf("Nhap vao so dinh cua mang da cho:");
scanf("%d", &n);
printf("Nhap vao dinh phat:");scanf("%d", &s);
printf("\nNhap vao dinh thu:");scanf("%d", &t);
if(n>max) return 1;
printf("Nhap vao quan he cua cac dinh theo quy tac\n\n\n");
printf("\t -c[i, j] neu i di toi j");
printf("\nA[i, j]=| ");
printf("\n\t -0 trong truong hop con lai\n\n\n");
for(i=0; i<n; ++i){
for(j=0; j<n; ++j){
printf("A[%d][%d]=", i+1, j+1);
scanf("%d", &A[i][j]);
f[i][j]=0;
}
}
return 0;
}
int PrintNetwork(){
//Print Network into matrix stype
int i, j;
for(i=0; i<n; ++i){
for(j=0; j<n; ++j){
printf(" %3d", A[i][j]);
}
printf("\n");
}
return 0;
}
int size(){
//size of quene
return (max-fr+r);
}
int isEmpty(){
//quene is empty?
return (fr=r);
}
int enquene(int m){
//insert m to quene
if(size()>max) printf("Hang doi day");
else{
Q[r]=m;
r++;
}
return m;
}
int dequene(){
//delete an element from quene
int m;
if(isEmpty()) printf("Hang doi rong");
else{
m=Q[fr];
fr++;
return m;
}
}
int min(int a, int b){
//minimum between a and b
if(a<b) return a;
else return b;
}
int FindPath(){
//Find augment path, return 1 if finding an augment path
int i=0, u, v;
for(i=0; i<n; ++i){
p[i]=-1;
}
p[s]=s; e[s]=1<<16;
enquene(s);
while(!isEmpty()){
u=dequene();
for(v=0; v<n; ++v){
if((A[u][v]>0)&&(f[u][v]<A[u][v])){
if(p[v]!=-1){
p[v]=u;
e[v]=min(e[u], A[u][v]-f[u][v]);
enquene(v);
if(v==t) break;
}
}
}
if((A[v][u]>0)&&(f[v][u]>0)){
if(p[v]!=-1){
p[v]=-u;
e[v]=min(e[u], f[v][u]);
enquene(v);
if(v==t) break;
}
}
}
if(p[t]>=0) return 1;
else return 0;
}
int Inc_Flow(){
//Increase flow along an augment path
int tang=e[t];
int v=p[t];
int u=t;
//printf("max");
while(u!=s){
if(v>0){
f[v][u]=f[v][u]+tang;
A[v][u]=A[v][u]-f[v][u];
A[u][v]=A[u][v]+f[v][u];
}
else{
v=-v;
f[u][v]=f[u][v]-tang;
A[u][v]=A[u][v]-f[u][v];
A[v][u]=A[v][u]+f[u][v];
}
u=v; v=p[u];
}
printf("f[2,5]= %d", f[2][5]);
return 0;
}
int main(){
int i, j, fmax=0;
printf("********************************************\n");
printf("\tBAI TAP LON MON TOAN ROI RAC\n");
printf("\t\tSinh vien thuc hien: Nguyen Ngoc Dat\n");
printf("\t\tSo hieu sinh vien: 20090676\n");
printf("********************************************\n");
printf("\t\t\t%c\t%c\n", 3, 3);
printf("\t>>>BAI TOAN LUONG CUC DAI TRONG MANG<<<\n");
if(initNetwork()) printf("So dinh nhap vao vuot qua so phan tu toi da cua mang");
printf("Ma tran trong so bieu dien mang:\n\n");
PrintNetwork();
int stop=0;
while(!stop){
if(FindPath()) Inc_Flow();
else stop=1;
}
i=0;
for(j=0; j<n; ++j){
if(A[i][j]!=0) fmax+=f[i][j];
}
printf("Luong cuc dai trong mang da cho la: %d", fmax);
getch();
return 0;
}

fbchicken
29-09-2011, 10:38 PM
Ngó thấy 2 lỗi, bạn cứ sửa đi rồi nếu chưa được mình tìm tiếp
1. if(p[v]!=-1){ (2 chỗ đều như vậy)
Tất cả gán =-1 hết, kiểm tra != -1 thì nó chạy đi đâu bây giờ :D
2. if((A[v][u]>0)&&(f[v][u]>0)){
Cái này sao lại bỏ ra ngoài vòng lặp for v

ngocvientk91
06-10-2011, 09:01 PM
vẫn k đc.

ai biết sửa dùm với đi

k thì có code tham khảo send mình với :D

G.Perelman
06-10-2011, 09:26 PM
Trước hết, hãy học cách nói câu "cảm ơn".