Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- using namespace std;
- const int N = 300;
- const int inf = 1'000'000'000;
- int n;
- int S, T;
- int M[N][N]; // из i-го в j-ое ребро пропускная способность
- bool F[N];
- int dfs(int v, int c = inf) {
- if (v == T) {
- return c;
- }
- F[v] = true;
- for (int a = 1; a <= n; a++) {
- if (M[v][a] > 0 && !F[a]) {
- int t = dfs(a, min(c, M[v][a]));
- if (t > 0) {
- M[v][a] -= t;
- M[a][v] += t;
- return t;
- }
- }
- }
- return 0;
- }
- int main() {
- cin >> n;
- cin >> S >> T;
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= n; j++) {
- cin >> M[i][j];
- }
- }
- int max_flow = 0;
- while (true) {
- for (int i = 1; i <= n; i++) {
- F[i] = false;
- }
- int flow = dfs(S);
- max_flow += flow;
- if (flow == 0) {
- break;
- }
- }
- cout << max_flow;
- return 0;
- }
- /*
- 7
- 1 7
- 0 3 0 0 2 0 0
- 0 0 2 1 0 0 0
- 0 0 0 0 0 0 4
- 0 0 0 0 0 0 3
- 0 0 0 0 0 5 0
- 0 0 0 0 0 0 1
- 0 0 0 0 0 0 0
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement