Source code :3 ~~~~~

include // for cin, cout

include // for file stream

include // for vector

include // for queue

using namespace std; // cài đặt BFS bằng ma trận kề void BFS_flow(vector<vector> & vvi, int source, int sink); // duyệt đồ thị theo chiều rộng int BFS_find_path(vector<vector> & vvi, int source, int sink); // duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh v void print_path(int v, int u); int WHITE = 0; // chưa thăm int BLACK = 2; // đã thăm xong int INF = int(1e8); int main(int argc, char * argv[]) // argc: argument count, argv: argument values { int n = 0; vector<vector> vvi; int i, j; cin >> n; vvi = vector<vector>(n, vector(n, 0)); // khai báo n vector, mỗi vector có n phần tử for (i = 0; i<n; i++) for (j = 0; j<n; j++) { cin >> vvi[i][j]; } int source, sink; cin >> source; cin >> sink; BFS_flow(vvi, source, sink); return 0; }
void BFS_flow(vector<vector> & vvi, int source, int sink) { int loops = 0; int result = 0; int path_cap; while (true) { loops++; path_cap = BFS_find_path(vvi, source, sink); if (path_cap>0) result += path_cap; else break; } cout << "Maximum flow is " << result << " after " << loops << " iterations."; } int BFS_find_path(vector<vector> & cap, int source, int sink) { int n = cap.size(); vector visited(n, WHITE); vector prev(n, -1); queue q; q.push(source); visited[source] = BLACK; // step 1: tìm đường đi từ đỉnh đến nguồn int where, from; while (!q.empty()) { where = q.front(); // get the vertex at the front of the queue q.pop(); // then pop it out of the queue if (where == sink) // found a pah break; for (int v = 0; v<n; v++) if ((cap[where][v]>0) && (WHITE == visited[v])) { prev[v] = where; visited[v] = BLACK; q.push(v); } } // step 2: find the corressponding flow where = sink; int path_cap = INF; while (prev[where]>-1) { from = prev[where]; path_cap = std::min(path_cap, cap[from][where]); where = from; } // step 3: update the residual network where = sink; while (prev[where]>-1) { from = prev[where]; cap[from][where] -= path_cap; cap[where][from] += path_cap; where = from; } if (path_cap != INF) return path_cap; return 0; } ~~~~~