




"""simple docstring"""



SCREAMING_SNAKE_CASE       = float("inf")




class 			UpperCAmelCase_						:




    def __init__(					self		: Any			,				snake_case_		: List[str]   )   ->							Optional[Any]:




     '''simple docstring'''

     A__ =       [0] * n
     A__ =       [0] * n
     A__ =       [0] * n
     A__ =       [[] for _ in range(snake_case_   )]




    def 							__magic_name__							(					self		: Union[str, Any]			,				snake_case_		: Optional[int]			,				snake_case_		: str			,				snake_case_		: str			,				snake_case_		: Optional[Any]=0   )   ->							Optional[Any]:




     '''simple docstring'''

     self.adj[a].append([b, len(self.adj[b]   ), c, 0]   )
     self.adj[b].append([a, len(self.adj[a]   ) - 1, rcap, 0]   )




    def 							__magic_name__							(					self		: List[Any]			,				snake_case_		: Tuple			,				snake_case_		: Union[str, Any]			,				snake_case_		: List[str]   )   ->							Dict:




     '''simple docstring'''

     if vertex == sink or not flow:
      return flow

     for i in range(self.ptr[vertex]			,				len(self.adj[vertex]   )   ):
      A__ =       self.adj[vertex][i]
      if self.lvl[e[0]] == self.lvl[vertex] + 1:
       A__ =       self.depth_first_search(e[0]			,				snake_case_			,				min(snake_case_			,				e[2] - e[3]   )   )
       if p:
        self.adj[vertex][i][3] += p
        self.adj[e[0]][e[1]][3] -= p
        return p
      A__ =       self.ptr[vertex] + 1
     return 0




    def 							__magic_name__							(					self		: Any			,				snake_case_		: Optional[Any]			,				snake_case_		: List[str]   )   ->							int:




     '''simple docstring'''

     A__,   A__ =       0, source
     for l in range(31   ):  # noqa: E741  l = 30 maybe faster for random data
      while True:
       A__,   A__ =       [0] * len(self.q   ), [0] * len(self.q   )
       A__,   A__,   A__ =       0, 1, 1
       while qi < qe and not self.lvl[sink]:
        A__ =       self.q[qi]
        qi += 1
        for e in self.adj[v]:
         if not self.lvl[e[0]] and (e[2] - e[3]) >> (30 - l):
          A__ =       e[0]
          qe += 1
          A__ =       self.lvl[v] + 1

       A__ =       self.depth_first_search(snake_case_			,				snake_case_			,				snake_case_   )
       while p:
        flow += p
        A__ =       self.depth_first_search(snake_case_			,				snake_case_			,				snake_case_   )

       if not self.lvl[sink]:
        break

     return flow
SCREAMING_SNAKE_CASE       = Dinic(10)
SCREAMING_SNAKE_CASE       = 0
SCREAMING_SNAKE_CASE       = 9
for vertex in range(1, 5):
      graph.add_edge(source, vertex, 1)
for vertex in range(5, 9):
      graph.add_edge(vertex, sink, 1)
for vertex in range(1, 5):
      graph.add_edge(vertex, vertex + 4, 1)

# Now we can know that is the maximum flow(source -> sink)
print(graph.max_flow(source, sink))











"""simple docstring"""



from manim import *




class 			UpperCAmelCase_						(		A_							):




    def 							__magic_name__							(					self		: Any   )   ->							Optional[int]:




     '''simple docstring'''

     A__ =       Rectangle(height=0.5			,				width=0.5   )
     A__ =       Rectangle(height=0.46			,				width=0.46   ).set_stroke(width=0   )
     A__ =       Rectangle(height=0.25			,				width=0.25   )

     A__ =       [mem.copy() for i in range(6   )]
     A__ =       [mem.copy() for i in range(6   )]
     A__ =       VGroup(*snake_case_   ).arrange(snake_case_			,				buff=0   )
     A__ =       VGroup(*snake_case_   ).arrange(snake_case_			,				buff=0   )
     A__ =       VGroup(snake_case_			,				snake_case_   ).arrange(snake_case_			,				buff=0   )
     A__ =       Text("CPU"			,				font_size=24   )
     A__ =       Group(snake_case_			,				snake_case_   ).arrange(snake_case_			,				buff=0.5			,				aligned_edge=snake_case_   )
     cpu.move_to([-2.5, -0.5, 0]   )
     self.add(snake_case_   )

     A__ =       [mem.copy() for i in range(4   )]
     A__ =       VGroup(*snake_case_   ).arrange(snake_case_			,				buff=0   )
     A__ =       Text("GPU"			,				font_size=24   )
     A__ =       Group(snake_case_			,				snake_case_   ).arrange(snake_case_			,				buff=0.5			,				aligned_edge=snake_case_   )
     gpu.move_to([-1, -1, 0]   )
     self.add(snake_case_   )

     A__ =       [mem.copy() for i in range(6   )]
     A__ =       VGroup(*snake_case_   ).arrange(snake_case_			,				buff=0   )

     A__ =       Text("Model"			,				font_size=24   )
     A__ =       Group(snake_case_			,				snake_case_   ).arrange(snake_case_			,				buff=0.5			,				aligned_edge=snake_case_   )
     model.move_to([3, -1.0, 0]   )
     self.add(snake_case_   )

     A__ =       []
     A__ =       []

     for i, rect in enumerate(snake_case_   ):
      rect.set_stroke(snake_case_   )

      A__ =       Rectangle(height=0.46 / 4			,				width=0.46 / 3   ).set_stroke(width=0.0   ).set_fill(snake_case_			,				opacity=0.7   )

      if i == 0:
       cpu_target.next_to(cpu_left_col_base[0].get_corner(DOWN + LEFT   )			,				buff=0.02			,				direction=snake_case_   )
       cpu_target.set_x(cpu_target.get_x() + 0.1   )
      elif i == 3:
       cpu_target.next_to(model_cpu_arr[0]			,				direction=snake_case_			,				buff=0.0   )
      else:
       cpu_target.next_to(model_cpu_arr[i - 1]			,				direction=snake_case_			,				buff=0.0   )
      self.add(snake_case_   )
      model_cpu_arr.append(snake_case_   )

     self.add(*snake_case_			,				*snake_case_   )

     A__ =       [meta_mem.copy() for i in range(6   )]
     A__ =       [meta_mem.copy() for i in range(6   )]
     A__ =       VGroup(*snake_case_   ).arrange(snake_case_			,				buff=0   )
     A__ =       VGroup(*snake_case_   ).arrange(snake_case_			,				buff=0   )
     A__ =       VGroup(snake_case_			,				snake_case_   ).arrange(snake_case_			,				buff=0   )
     A__ =       Text("Disk"			,				font_size=24   )
     A__ =       Group(snake_case_			,				snake_case_   ).arrange(snake_case_			,				buff=0.5			,				aligned_edge=snake_case_   )
     disk.move_to([-4.0, -1.25, 0]   )
     self.add(snake_case_			,				snake_case_   )

     A__ =       []

     for i in range(6   ):
      A__ =       fill.copy().set_fill(snake_case_			,				opacity=0.8   )
      target.move_to(disk_left_col_base[i]   ).scale(0.5   )
      cpu_disk_arr.append(snake_case_   )

     self.add(*snake_case_   )

     A__ =       Square(side_length=2.2   )
     key.move_to([-5, 2, 0]   )

     A__ =       MarkupText(
         F"""<b>Key:</b>\n\n<span fgcolor='{YELLOW}'>●</span> Empty Model"""			,				font_size=18			,				)

     key_text.move_to([-5, 2.4, 0]   )

     self.add(snake_case_			,				snake_case_   )

     A__ =       MarkupText(
         F"""<span fgcolor='{BLUE}'>●</span> Checkpoint"""			,				font_size=18			,				)

     blue_text.next_to(snake_case_			,				DOWN * 2.4			,				aligned_edge=key_text.get_left()   )
     self.add(snake_case_   )

     A__ =       MarkupText(F"""The offloaded weights are all sent to the CPU."""			,				font_size=24   )
     step_a.move_to([2, 2, 0]   )

     self.play(Write(snake_case_			,				run_time=3   )   )

     for i in range(6   ):
      A__ =       cpu_disk_arr[i]
      A__ =       rect.copy().set_fill(snake_case_			,				opacity=0.8   ).scale(2.0   )
      cpa.generate_target()
      cpa.target.move_to(model_base[i]   )

      if i == 0:
       rect.set_fill(snake_case_			,				opacity=0.8   )
       rect.generate_target()
       rect.target.move_to(cpu_left_col_base[0]   ).scale(2.0   )

       self.remove(
           *snake_case_			,				*snake_case_			,				)

      else:
       rect.generate_target()
       rect.target.move_to(cpu_left_col_base[i]   ).scale(2.0   )
      self.play(MoveToTarget(snake_case_   )			,				MoveToTarget(snake_case_   )			,				model_base[i].animate.set_stroke(snake_case_   )   )
     self.play(FadeOut(snake_case_   )   )

     A__ =       MarkupText(
         F"""Finally, hooks are added to each weight in the model\nto transfer the weights from CPU to GPU\n\t\tand back when needed."""			,				font_size=24			,				)
     step_a.move_to([2, 2, 0]   )

     self.play(Write(snake_case_			,				run_time=3   )   )

     A__ =       []
     A__ =       []
     for i in range(6   ):
      A__ =       Arrow(start=snake_case_			,				end=snake_case_			,				color=snake_case_			,				buff=0.5   )
      a.next_to(model_base[i].get_left()			,				snake_case_			,				buff=0.2   )
      arrows.append(snake_case_   )
      animations.append(Write(snake_case_   )   )
     self.play(*snake_case_   )
     self.wait()





