首页 > 代码库 > OIer-Dinic
OIer-Dinic
1 class Network { 2 private : 3 struct edge { 4 int to, w, nxt ; 5 edge ( ) { } 6 edge ( int to, int w, int nxt ) : to ( to ), w ( w ), nxt ( nxt ) { } 7 } g [N << 1] ; 8 9 int head [N], cur [N], ecnt ; 10 int S, T , dep [N] ; 11 12 inline int Dfs ( int u, int a ) { 13 if ( u == T || ! a ) return a ; 14 int flow = 0, v, f ; 15 for ( int& i = cur [u] ; i ; i = g [i].nxt ) { 16 v = g [i].to ; 17 if ( dep [v] == dep [u] + 1 ) { 18 f = Dfs ( v, min ( g [i].w, a - flow ) ) ; 19 g [i].w -= f, g [i ^ 1].w += f ; 20 flow += f ; 21 if ( a == flow ) return a ; 22 } 23 } 24 if ( ! flow ) dep [u] = -1 ; 25 return flow ; 26 } 27 28 inline bool Bfs ( int S, int T ) { 29 static std :: queue < int > q ; 30 memset ( dep, 0, sizeof ( int ) * ( T + 1 ) ) ; 31 dep [S] = 1 ; 32 q.push ( S ) ; 33 while ( ! q.empty ( ) ) { 34 int u = q.front ( ) ; q.pop ( ) ; 35 for ( int i = head [u] ; i ; i = g [i].nxt ) { 36 int v = g [i].to ; 37 if ( g [i].w && ! dep [v] ) { 38 dep [v] = dep [u] + 1 ; 39 q.push ( v ) ; 40 } 41 } 42 } 43 return dep [T] ; 44 } 45 public : 46 Network ( ) { ecnt = 1 ; } 47 48 inline void Add_edge ( int u, int v, int w ) { 49 g [++ ecnt] = edge ( v, w, head [u] ) ; head [u] = ecnt ; 50 g [++ ecnt] = edge ( u, 0, head [v] ) ; head [v] = ecnt ; 51 } 52 53 inline int Dinic ( int S, int T ) { 54 this -> S = S, this -> T = T ; 55 int rt = 0 ; 56 while ( Bfs ( S, T ) ) { 57 memcpy ( cur, head, sizeof ( int ) * ( T + 1 ) ) ; 58 rt += Dfs ( S, 0x3f3f3f3f ) ; 59 } 60 return rt ; 61 } 62 } Lazer ;
OIer-Dinic
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。