Go Back   VN-Zoom forum > Chia sẻ kiến thức > Lập trình > Pascal | C/C++

 

Tại sao bạn không thử viết 1 bài viết trong Vn-Zoom nhỉ?

Trả lời
 
Ðiều Chỉnh Xếp Bài
Old 09-06-2008, 13:12   #1
Búa Gỗ
 
vejo's Avatar
 
Tham gia: May 2008
Bài: 10
VZD: 581
Cảm ơn: 4
Điểm: 10/3 bài viết
Default Giúp em xử lý bài C (luồng cực đại) này với các anh ơi :((

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();
}
----------------
vejo vẫn chưa có mặt trong diễn đàn   Trả Lời Với Trích Dẫn
Trả lời

Ðiều Chỉnh
Xếp Bài

Quyền Sử Dụng Ở Diễn Ðàn
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is Mở
Smilies đang Mở
[IMG] đang Mở
HTML đang Tắt
Trackbacks are Tắt
Pingbacks are Tắt
Refbacks are Tắt
Chuyển đến


Múi giờ GMT +7. Hiện tại là 03:08.


Powered by vBulletin® Version 3.7.3
Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
vBCredits v1.4 Copyright ©2007 - 2008, PixelFX Studios
Từ điển được cung cấp bởi VDict.com - Hosting được tài trợ bởi Rao vặt 123