Dinitz algorithm for finding the maximum flow

Question

Dinitz algorithm for finding the maximum flow

Hello, on emax I found an implementation of maximum flow in c++ using adjacency matrices:http://e-maxx.ru/algo/dinic . I used this code for the task, but it returned the wrong answer.What is my mistake?

int main(){
    ios_base::sync_with_stdio(0);
    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; ++i){
        int a,b,cap;
        cin >> a >> b >> cap;
        c[a][b] = cap;
    }
    cin >> s >> t;
    cout << dinic;
    return 0;
}

Input data:

4  //количесво вершин 
4  //количетсво дуг
1 2 1  // a,b,c.Ребро из вершины a в вершину b с пропускной способностью c
2 3 2
1 4 2
4 3 1
1  //исток
3  //сток

Output data:

1

c++графы

Author: Elmir, 2016-06-26

Source

1 answers

score 4 · Accepted Answer

The errors in the above code are as follows:

You output cout << dinic, but dinic is not a function call, it is a pointer to a function. Unfortunately, cout behaves strangely with them, and always outputs the unit, and not, in fact, the address of the function. If you compile with all the warnings enabled (the -Wall key, if you use GCC and /Wall in Visual C++), the compiler may report that something is wrong in this line. To call a function in C++, you need parentheses after the name - dinic(), then the function will be called and the result will be returned.
First, you don't read the number of edges from the input file anywhere, but rather assume that there are n as many edges as there are vertices, and the descriptions of the edges come right after the number of vertices. This does not correspond to the format of the example you gave: there the number of edges is written separately.
In C++ programs, array elements (including two-dimensional ones) are usually numbered from zero. The same principle corresponds to implementation of the Dinitz algorithm on e-maxx-vertices have numbers from 0 to n-1. When reading, you think that the vertices are numbered from 1 to n-1, so the vertex with the number n is not taken into account by the algorithm or is taken into account crookedly.