class Network {
private :
struct edge {
int to, w, nxt ;
edge ( ) { }
edge (
int to,
int w,
int nxt ) : to ( to ), w ( w ), nxt ( nxt ) { }
} g [N <<
1] ;
int head [N], cur [N], ecnt ;
int S, T , dep [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, 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 ) {
static std ::
queue < int > q ;
memset ( dep,
0,
sizeof (
int ) * ( T +
1 ) ) ;
dep [S] =
1 ;
q.push ( S ) ;
while ( ! q.empty ( ) ) {
int u = q.front ( ) ; q.pop ( ) ;
for (
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.push ( 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 ;
}
inline int Dinic (
int S,
int T ) {
this -> S = S,
this -> T = T ;
int rt =
0 ;
while ( Bfs ( S, T ) ) {
memcpy ( cur, head,
sizeof (
int ) * ( T +
1 ) ) ;
rt += Dfs ( S,
0x3f3f3f3f ) ;
}
return rt ;
}
} Lazer ;
