Приложение а

(обязательное)

Текст основного файла

#include"ff_alg.h"

int main()

{

clock_t time = clock();

read_input_file();

printf("%d\n",max_flow(0,n-1));

time = clock() - time;

cout<<time<<endl;

system("pause");

return 0;

}

Приложение б

(обязательное)

Текст включаемого файла

#include<stdio.h>

#include<iostream>

#include<time.h>

using namespace std;

#ifdef _DEBUG

#undef _DEBUG

#include <omp.h>

#define _DEBUG

#else

#include <omp.h>

#endif

#define WHITE 0

#define GRAY 1

#define BLACK 2

#define MAX_NODES 100

#define INFINITY 10000

int min (int x, int y);

void enqueue (int x);

int dequeue () ;

int bfs (int start, int target) ;

int max_flow (int source, int sink);

int n;

int e;

int capacity[MAX_NODES][MAX_NODES];

int flow[MAX_NODES][MAX_NODES];

int color[MAX_NODES];

int pred[MAX_NODES];

int head,tail;

int q[MAX_NODES+2];

int min (int x, int y) {return x<y ? x : y;}

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[u] = WHITE;

}

head = tail = 0;

enqueue(start);

pred[start] = -1;

omp_set_num_threads(32);

#pragma omp parallel

while (head!=tail)

{

u = dequeue();

//#pragma omp for

for (v=0; v<n; v++)

{

if (color[v]==WHITE && capacity[u][v]-flow[u][v]>0)

{

enqueue(v);

pred[v] = u;

}

}

}

return color[target]==BLACK;

}

int max_flow (int source, int sink) {

int u;

int max_flow = 0;

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

flow[i][j] = 0;

}

}

omp_set_num_threads(32);

//#pragma omp parallel

while (bfs(source,sink))

{

int increment = INFINITY;

//#pragma omp for

for (u=n-1; pred[u]>=0; u=pred[u])

{

increment = min(increment,capacity[pred[u]][u]-flow[pred[u]][u]);

}

#pragma omp for

for (u=n-1; pred[u]>=0; u=pred[u])

{

flow[pred[u]][u] += increment;

flow[u][pred[u]] -= increment;

}

max_flow += increment;

}

return max_flow;

}

void read_input_file()

{

int a,b,c;

FILE* input = fopen("C:\\data.txt","r");

fscanf_s(input,"%d %d",&n,&e);

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

capacity[i][j] = 0;

}

}

for (int i = 0; i < e; i++)

{

fscanf_s(input,"%d %d %d",&a,&b,&c);

capacity[a][b] = c;

}

fclose(input);

}