#include <stdio.h>
#include <stdlib.h>

typedef char	Boolean;
#define TRUE	1
#define FALSE	0

#define NMAX	20

Boolean FindPath( short s, double *dpMin, short *path, short nPoint);
void Zastavka( void);
void InputMatrix( void);
void CopyMatrix( void);
void PrintResult( short nIter, double dThetta, short *path);

#define MAXDOUBLE	(1.0e+90)

typedef double	Matrix[NMAX+1][NMAX+1];

#ifndef min
	#define min(a,b)	((a)<(b) ? (a) : (b))
#endif

Matrix	c, c1;
short	n;

#define cpInputFileName 	"input.dat"
#define cpOutputFileName	"output.dat"

void main()
{
	short	nIter;
	double	dMin;
	Boolean bContinue;
	short	path[NMAX];

	Zastavka();
	InputMatrix();
	CopyMatrix();
	path[0] = nIter = 0;
	PrintResult( nIter, dMin, path);
	do
	{
		dMin = MAXDOUBLE;
		bContinue = FindPath( 0, &dMin, path, 1);
		PrintResult( ++nIter, bContinue ? dMin : 0, path);
	}
	while( bContinue);
}

/******************************************************
	FindPath


******************************************************/
Boolean FindPath( short s, double *dpMin, short *path, short nPoint)
{
	short	i;
	Boolean bRetV = FALSE;
	double	dThetta;

	for( i = n; i> 0 && !bRetV; i--)
	{
		if( i == s) continue;
		if( c[s][i] > 0 && !c[i][i])
		{
			c[i][i] = TRUE;
			dThetta = min( *dpMin, c[s][i]);
			if( i == n)
				bRetV = TRUE;
			else
				bRetV = FindPath( i, &dThetta, path, nPoint+1);
			c[i][i] = FALSE;
		}
	}
	if( bRetV)
	{
		i++; *dpMin = dThetta;
		path[nPoint] = i;
		c[s][i] -= dThetta;
		c[i][s] += dThetta;
	}
	return( bRetV);
}

/******************************************************
	InputMatrix


******************************************************/
void InputMatrix()
{
	short	i, j;
	FILE	*in;

	in = fopen( cpInputFileName, "r");
	fscanf( in, "%d", &n);
	if( n > NMAX)
	{
		printf( "Превышение размерности!\n");
		exit( 1);
	}

	for( i = 0; i <= n; i++)
		for( j = 0; j <= n; j++)
			fscanf( in, "%lf", &c[i][j]);
	for( i = 0; i <= n; i++) c[i][i] = FALSE;
	fclose( in);
}

/******************************************************
	CopyMatrix


******************************************************/
void CopyMatrix()
{
	short	i, j;

	for( i = 0; i <= n; i++)
		for( j = 0; j <= n; j++)
			c1[i][j] = c[i][j];
}

/******************************************************
	PrintResult


******************************************************/
void PrintResult( short nIter, double dThetta, short *path)
{
	short	i, j;
	FILE	*out;

	out = fopen( cpOutputFileName, (nIter > 0) ? "a" : "w");

	if( dThetta == 0)
	{
		fprintf( out, "\n********** Получен результат **********\n");
		for( i = 0; i <= n; i++)
			for( j = 0; j <= n; j++)
			{
				if( c1[i][j] > c[i][j])
					fprintf( out, " p( %2d; %2d) = %lf;\n",
										i, j, c1[i][j] - c[i][j]);
			}
		dThetta = 0;
		for( j = 0; j <= n; j++)
			if( c1[0][j] > c[0][j]) dThetta += c1[0][j] - c[0][j];
		fprintf( out, "\nМаксимальная пропускная способность: %lf\n", dThetta);
	}
	else
	{
		if( nIter)
			fprintf( out, "\n\t********** После %d-ой итерации **********\n", nIter);
		else
			fprintf( out, "\t\t\t********** Исходная матрица **********\n");
		fprintf( out, "-----+");
		for( i = 0; i <= n; i++)
			 fprintf( out, "----------+");
		fprintf( out, "\n     |");
		for( i = 0; i <= n; i++)
			 fprintf( out, "    %5d |", i);
		fprintf( out, "\n-----+");
		for( i = 0; i <= n; i++)
			 fprintf( out, "----------+");
		fprintf( out, "\n");
		for( i = 0; i <= n; i++)
		{
			fprintf( out, " %3d |", i);
			for( j = 0; j <= n; j++)
			if( c[i][j] == c1[i][j])
				fprintf( out, " %5lf |", c[i][j]);
			else if( c[i][j] > c1[i][j])
				fprintf( out, "<%5lf>|", c[i][j]);
			else
				fprintf( out, ">%5lf<|", c[i][j]);
			fprintf( out, "\n");
		}
		fprintf( out, "-----+");
		for( i = 0; i <= n; i++)
			 fprintf( out, "----------+");
		fprintf( out, "\n");

		if( nIter)
		{
			fprintf( out, "Найден путь: ( ");
			for( i = 0; path[i] < n; i++)
				fprintf( out, "%d->", path[i]);
			fprintf( out, "%d )\n", n);

			fprintf( out, "Значение минимального элемента: %lf\n", dThetta);
		}
		else
		{
			fprintf( out, ">ЗНАЧЕНИЕ< - значение элемента уменьшилось.\n");
			fprintf( out, "<ЗНАЧЕНИЕ> - значение элемента увеличилось.\n");
		}
	}
	fclose( out);
}

void Zastavka()
 {
     printf( "\t			НГТУ\n\n\n");
     printf( "\t	   Кафедра прикладной математики\n\n\n");
     printf( "\t		  Курсовой проект\n");
     printf( "\t\"Алгоритм Форда-Фалкерсона поиска максимального потока\n");
     printf( "\t		в транспортной сети\"\n\n\n\n");
     printf( "\tФакультет: ФПМИ\n\n");
     printf( "\tГруппа	 : АП-11\n\n");
     printf( "\tСтудент  : Сазонов М.В.\n\n\n\n");
     printf( "\t		       1995г.\n\n\n\n");

 }
