Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Self loop handling #1

Closed
yosupo06 opened this issue Sep 8, 2020 · 0 comments · Fixed by #12
Closed

Self loop handling #1

yosupo06 opened this issue Sep 8, 2020 · 0 comments · Fixed by #12

Comments

@yosupo06
Copy link
Collaborator

yosupo06 commented Sep 8, 2020

Reporter: Mi_Sawa (Japanese tweet: https://twitter.com/Mi_Sawa/status/1303170874938331137)

max_flow / min_cost_flow cannot handle self-loops "correctly".

This is the code of max_flow.add_edge(). We can notice that we cannot handle an id of reverse edge correctly.
In now, in spite of this code wrong, everything goes well. However, cleary we should fix this.

    int add_edge(int from, int to, Cap cap) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        assert(0 <= cap);
        int m = int(pos.size());
        pos.push_back({from, int(g[from].size())});
        g[from].push_back(_edge{to, int(g[to].size()), cap});
        g[to].push_back(_edge{from, int(g[from].size()) - 1, 0});
        return m;
    }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant