/*
	© MATTO MATTI 2019
	http://mattomatti.com/pl/a0280
	napisane przy użyciu Visual Studio Community 2015
	2019-07-20 v 1.0
*/

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

struct dane {
	int odleglosc;
	int poprzednik;
};

dane* BFS(int** macierz, int n, int start) {
	dane* tab = new dane[n];
	for (int i = 0; i < n; i++) {
		tab[i].odleglosc = INT32_MAX;
		tab[i].poprzednik = -1;
	}
	tab[start].odleglosc = 0;
	queue<int> q;
	q.push(start);
	while (q.size() != 0) {
		int u = q.front();
		q.pop();
		for (int i = 0; i < n; i++) {
			if (macierz[u][i] > 0 && tab[i].odleglosc == INT32_MAX) {
				tab[i].odleglosc = tab[u].odleglosc + 1;
				tab[i].poprzednik = u;
				q.push(i);
			}
		}
	}
	return tab;
}

int AlgorytmDinitza(int** macierz, int n, int start, int koniec) {
	int f = 0;
	while (true) {
		dane* tab = BFS(macierz, n, start);
		if (tab[koniec].odleglosc == INT32_MAX)
			return f;
		int f_sciezka = INT32_MAX;
		int teraz = koniec;
		while (teraz != start) {
			int rodzic = tab[teraz].poprzednik;
			f_sciezka = min(macierz[rodzic][teraz], f_sciezka);
			teraz = rodzic;
		}
		teraz = koniec;
		while (teraz != start) {
			int rodzic = tab[teraz].poprzednik;
			macierz[rodzic][teraz] -= f_sciezka;
			teraz = rodzic;
		}
		f += f_sciezka;
	}
}

int main() {
	int n, s, t;
	cout << "Podaj ile jest wierzcholkow w grafie\n n = ";
	cin >> n;
	cout << "Podaj wezel poczatkowy\n s = ";
	cin >> s;
	cout << "Podaj wezel koncowy\n t = ";
	cin >> t;
	int** macierz = new int*[n];
	for (int i = 0; i < n; i++) {
		macierz[i] = new int[n];
		for (int j = 0; j < n; j++) {
			cin >> macierz[i][j];
		}
	}
	int przeplyw = AlgorytmDinitza(macierz, n, s, t);
	cout << "Maksymalny przeplyw wynosi: " << przeplyw;
	system("pause");
	return 0;
}