السلام عليكم
ارجو ممن لديهم خبرة المساعدة في اكتشاف الخطا وتصحيحه
انا احاول تنفيد خوارزمية فورد
maximum flow
Ford-Fulkerson algorithm
وبحثت في النت ووجدت كودات ولم استطيع تنفيد احدهم وكل واحد بيه خطا اقلها خطا واحد ارجو ممكن لديهم الخبرة المساعدة ، لانه عندي مشروع يجب ان اسلم الاسبوع المقبل
واول برنامج يحتوي خطا
too much global data defined in file
والرنامج هو :
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX_NODES 100
#define oo 1000000000
#include<stdio.h>
int n; // number of nodes
int e; // number of edges
int capacity[MAX_NODES][MAX_NODES]; // capacity matrix
int flow[MAX_NODES][MAX_NODES]; // flow matrix
int color[MAX_NODES]; // needed for breadth-first search
int pred[MAX_NODES]; // array to store augmenting path
int min (int x, int y) {
return x<y ? x : y; // returns minimum of x and y
}
int head,tail;
int q[MAX_NODES+2];
void enqueue (int x) {
q[tail] = x;
tail++;
color[x] = GRAY;
}
int dequeue () {
int x = q[head];
head++;
color[x] = BLACK;
return x;
}
int bfs (int start, int target) {
int u,v;
for (u=0; u<n; u++) {
color = WHITE;
}
head = tail = 0;
enqueue(start);
pred[start] = -1;
while (head!=tail) {
u = dequeue();
// Search all adjacent white nodes v. If the capacity
// from u to v in the residual network is positive,
// enqueue v.
for (v=0; v<n; v++) {
if (color[v]==WHITE && capacity[v]-flow[v]>0) {
enqueue(v);
pred[v] = u;
}
}
}
// If the color of the target node is black now,
// it means that we reached it.
return color[target]==BLACK;
}
int max_flow (int source, int sink) {
int i,j,u;
// Initialize empty flow.
int max_flow = 0;
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
flow[j] = 0;
}
}
// While there exists an augmenting path,
// increment the flow along this path.
while (bfs(source,sink)) {
// Determine the amount by which we can increment the flow.
int increment = oo;
for (u=n-1; pred>=0; u=pred) {
increment = min(increment,capacity[pred]-flow[pred]);
}
// Now increment the flow.
for (u=n-1; pred>=0; u=pred) {
flow[pred] += increment;
flow[pred] -= increment;
}
max_flow += increment;
}
// No augmenting path anymore. We are done.
return max_flow;
}
void read_input_file() {
int a,b,c,i,j;
FILE* input = fopen("mf.in","r");
// read number of nodes and edges
fscanf(input,"%d %d",&n,&e);
// initialize empty capacity matrix
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
capacity[j] = 0;
}
}
// read edge capacities
for (i=0; i<e; i++) {
fscanf(input,"%d %d %d",&a,&b,&c);
capacity[a] = c;
}
fclose(input);
}
int main () {
read_input_file();
printf("%d\n",max_flow(0,n-1));
return 0;
}
#include <string.h>
// the maximum number of vertices
#define NN 100
// adjacency matrix (fill this up)
int cap[NN][NN];
// flow network
int fnet[NN][NN];
// BFS
int q[NN], qf, qb, prev[NN];
int fordFulkerson( int n, int s, int t )
{
// init the flow network
memset( fnet, 0, sizeof( fnet ) );
int flow = 0;
while( true )
{
// find an augmenting path
memset( prev, -1, sizeof( prev ) );
qf = qb = 0;
prev[q[qb++] = s] = -2;
while( qb > qf && prev[t] == -1 )
for( int u = q[qf++], v = 0; v < n; v++ )
if( prev[v] == -1 && fnet[v] - fnet[v] < cap[v] )
prev[q[qb++] = v] = u;
// see if we're done
if( prev[t] == -1 ) break;
// get the bottleneck capacity
int bot = 0x7FFFFFFF;
for( int v = t, u = prev[v]; u >= 0; v = u, u = prev[v] )
bot <?= cap[v] - fnet[v] + fnet[v];
// update the flow network
for( int v = t, u = prev[v]; u >= 0; v = u, u = prev[v] )
fnet[v] += bot;
flow += bot;
}
return flow;
}
//----------------- EXAMPLE USAGE -----------------
int main()
{
memset( cap, 0, sizeof( cap ) );
int numVertices = 100;
// ... fill up cap with existing edges.
// if the edge u->v has capacity 6, set cap[v] = 6.
cout << fordFulkerson( numVertices, s, t ) << endl;
return 0;
}
