---
# System prepended metadata

title: Algo｜FLOW 演算法
tags: [Algo]

---

# FLOW 演算法
- Dinic 演算法
    ```clike=
    struct Dinic{
        static const int MXN = 10000;
        struct Edge{ int v,f,re; }; // 指向點, 容量, 反向邊的 ID

        int n,s,t,level[MXN];
        vector<Edge> E[MXN];

        void init(int _n, int _s, int _t){
            n = _n; s = _s; t = _t;
            for (int i=0; i<n; i++) E[i].clear();
        }
        void add_edge(int u, int v, int f){
            E[u].push_back( {v,f,E[v].size()}   );
            E[v].push_back( {u,0,E[u].size()-1} );
        }

        // 建構分層圖
        bool BFS(){
            for (int i=0; i<n; i++) level[i] = -1;
            queue<int> que;
            que.push(s);
            level[s] = 0;
            while (!que.empty()){
                int u = que.front(); que.pop();
                for (auto it : E[u]){
                    if (it.f > 0 && level[it.v] == -1){
                        level[it.v] = level[u]+1;
                        que.push(it.v);
                    }
                }
            }
            return level[t] != -1;
        }

        // 在分層圖中，找出一條從 u 出發流量不超過 res_flow 的增廣路
        int DFS(int u, int res_flow){
            if (u == t) return res_flow;
            int res = 0;
            for (auto &it : E[u]){
                if (it.f > 0 && level[it.v] == level[u]+1){
                    int tmp = DFS(it.v, min(res_flow, it.f));
                    res += tmp; 
                    res_flow -= tmp; 
                    it.f -= tmp;
                    E[it.v][it.re].f += tmp;
                    if (res_flow == 0) return res;
                }
            }
            if (!res) level[u] = -1;
            return res;
        }
        int flow(){
            int res = 0;
            while ( BFS() )
                res += DFS(s,2147483647);
            return res;
        }
    } flow;
    ```

