![]() |
|
|||||||
|   |
![]() |
|
|
Ðiều Chỉnh | Xếp Bài |
|
|
#1 |
|
Búa Gỗ
![]() Tham gia: May 2008
Bài: 10
VZD: 581
Cảm ơn: 4
Điểm: 10/3 bài viết
|
Hic! Sắp đến ngày nộp bài rồi mà bài của em vẫn chưa chạy. Bác nào giúp em sửa lại cho nó chạy với. Em cám ơn nhiêu!
<Dây là 1 bài toán về luồng cực đại >------- #include <stdio.h> #include <conio.h> #include <math.h> #include <stdlib.h> #include <process.h> #define MAX 100 #define oo 100 FILE *f1; FILE *f2; int c[MAX][MAX], *(f[MAX][MAX]); int Label[MAX]; int n,s,t; void Input() { int m,i,j,u,v; f1=fopen("MAXFLOW.INP","rt"); fscanf(f1,"%d%d%d%d",&n,&m,&s,&t); for(i=1;i<=n;i++) for(j=1;j<=n;j++) c[i][j]=0; for(i=1;i<=m;i++) { fscanf(f1,"%d%d",&u,&v); fscanf(f1,"%d",&c[u][v]); } fclose(f1); } int FindPath(void) { int u,v,i; int Queue[MAX]; int First=1,Last=1; for (i=1;i<=n;i++) Label[i]=0; Queue[First]=s; Label[s]=n+1; while(First<=Last) { u=Queue[First]; First++; for(v=1;v<=n;v++) if ((Label[v]==0) && (c[u][v] > *(f[u][v]) ) ) {Label[v]=u; if(v==t) return(1); Last++; Queue[Last]=v; } } return(0); } void IncFlow() { int delta,u,v; delta=oo; v=t; do{ u=Label[v]; if((c[u][v] - *(f[u][v]) ) < delta) delta=c[u][v] - *(f[u][v]); v=u; }while(v!=s); v=t; do{ u=Label[v]; *(f[u][v]) = *(f[u][v]) + delta; *(f[v][u]) = *(f[v][u]) - delta; v=u; } while(v!=s); } void Output() { int u,v,k; f2=fopen("MAXFLOW.OUT","wt"); k=0; for (u=1;u<=n;u++) for (v=1;v<=n;v++) if (*(f[u][v]) > 0) if (u==s) k = k + *(f[s][v]); fprintf(f2,"%d \n",k); for(u=1;u<=n;u++) for(v=1;v<=n;v++) if(*(f[u][v]) > 0) fprintf(f2,"(%d --> %d) %d\n",u,v,*(f[u][v])); fclose(f2); } main() { int i,j; clrscr(); Input(); for(i=1;i<=n;i++) for(j=1;j<=n;j++) *(f[i][j])=0; while(1<2) { if(FindPath()==0) break; IncFlow(); } Output(); } ---------------- |
|
|
|