网络流Dinic模板

之前的被卡常数了……

class Network  {
private :
    struct edge  {
        int to, w, nxt ;
        edge ( ) {        }
        edge ( int to, int w, int nxt ) : to ( to ), w ( w ), nxt ( nxt ) {        }  
    } g [M << 1] ;

    int head [N], cur [N], ecnt ;
    int S, T, n, dep [N], q [N] ;

    inline int dfs ( int u, int a )  {
        if ( u == T || ! a )  return a ;
        int flow = 0, v, f ;
        for ( int& i = cur [u] ; i ; i = g [i].nxt )  {
            v = g [i].to ;
            if ( dep [v] == dep [u] + 1 )  {
                f = dfs ( v, std :: min ( g [i].w, a - flow ) ) ;
                g [i].w -= f, g [i ^ 1].w += f ;
                flow += f ;
                if ( a == flow )  return a ;
            }
        }
        if ( ! flow )  dep [u] = -1 ;
        return flow ;
    }

    inline bool bfs ( int S, int T )  {
        memset ( dep, 0, sizeof ( int ) * ( n + 1 ) ) ;
        dep [S] = 1 ;
        register int fr ( 0 ), tl ( 0 ) ;
        q [++ tl] = S ;
        while ( fr ^ tl )  {
            int u = q [++ fr] ;
            for ( register int i = head [u] ; i ; i = g [i].nxt )  {
                int& v = g [i].to ;
                if ( g [i].w &&  ! dep [v] )  {
                    dep [v] = dep [u] + 1 ;
                    q [++ tl] = v ;
                }
            }
        }
        return dep [T] ;
    }
public :
    Network ( )  {    ecnt = 1 ; }

    inline void add_edge ( int u, int v, int w )  {
        g [++ ecnt] = edge ( v, w, head [u] ) ;     head [u] = ecnt ;
        g [++ ecnt] = edge ( u, 0, head [v] ) ;     head [v] = ecnt ;
    }

    int dinic ( int S, int T, int n )  {
        this -> S = S, this -> T = T, this -> n = n ;
        int rt = 0, f ;
        while ( bfs ( S, T ) )    {
            memcpy ( cur, head, sizeof ( int ) * ( n + 1 ) ) ; 
            while ( ( f = dfs ( S, oo ) ) )  rt += f ;
        }
        return rt ;
    }
} Lazer ;