PDA

View Full Version : Bài toán luồng cực đại trong mạng?, help me!!!



ariellove
03-05-2009, 14:33
Có bạn nào học về bài toán luồng cực đại trong mạng chưa vậy? Mình có code bài đó mà ko hiểu,các bạn giúp mình với!
Đây là code :.

// CHUONG TRINH NAY CHAY TOT TREN BC31
#include <conio.h>
#include <stdio.h>
#include <iostream.h>
#define max 100
int c[max][max],f[max][max],d[max],p[max];
int pathfound,n,m,s,t;

void Nhapsolieu()
{
FILE *ftext;
int u,v;
// clrscr();
ftext=fopen("D:\\FM.inp","rt");
fscanf(ftext,"%d%d%d%d",&n,&m,&s,&t);
for (int i=1;i<=m;i++)
{
fscanf(ftext,"%d",&u);
fscanf(ftext,"%d",&v);
fscanf(ftext,"%d",&c[u][v]);
}
fclose(ftext);
}

int min(int a,int b)
{
if (a< b) return a;
return b;
}

void Find_path()
{
int nvt=1,u,vt[max];
for (int i=1;i<=max;i++)
{p[i]=0;d[i]=0;}
p[s]=s;
d[s]=max;
vt[nvt]=s;
pathfound=1;
while (nvt!=0)
{
u=vt[nvt--];
for (int v=1;v<=n;v++)
if (p[v]==0)
{
if (c[u][v]>0 && f[u][v]<c[u][v])
{
p[v]=u;
d[v]=min(d[u],c[u][v]-f[u][v])...
vt[++nvt]=v;
if (v==t) return;
}
if (c[v][u]>0 && f[v][u]>0)
{

p[v]=-u;
d[v]=min(d[u],f[v][u]);
vt[++nvt]=v;
if (v==t) return;
}
}
}
pathfound=0;
}

void Inc_flow()
{
int v=p[t],u=t,tang=d[t];
while (u!=s)
{
if (v>0) f[v][u]+=tang;
else
{
v=-v;
f[u][v]-=tang;
}
u=v;
v=p[u];
}
}

void Max_flow()
{int stop=0;
while (stop==0)
{
Find_path();
if (pathfound==1) Inc_flow();
else stop=1;
}
}

void main()
{ Nhapsolieu();
Max_flow();
int valf=0;
for (int u=1;u<=n;u++)
if (c[s][u]>0)
valf+=f[s][u];
cout<<"Ma tran c va f ket qua(dinh dau, dinh cuoi,Tai nang, luong tren canh):\n";
for (int u=1;u<=n;u++)
for (int v=1;v<=n;v++)
if (c[u][v]>0)
cout<<u<<" "<<v<<" "<<c[u][v]<<" "<<f[u][v]<<endl;
cout<<"Gia tri cuc dai cua luong trong mang la :"<<valf;
getch();
}

Mình muốn hỏi trong bài toán này người ta tính f[u][v] như thế nào? Nguyên tắc hoạt động bài toán này như thế nào? Tính luồng cực đại như thế nào?
Xin cảm ơn!