class MaxFlow:
    def __init__(self, graph):
        """
        初始化最大流求解器。
        :param graph: 邻接表表示的图。例如：{'s': {'A': 10, 'B': 5}, 'A': {'B': 15, 't': 10}, ...}
        """
        self.graph = graph # 原始容量图
        self.flow = {}     # 存储当前流，格式与graph相同，但存储流量值
        self._init_flow()
        
    def _init_flow(self):
        """初始化流量图，所有边的流量初始为0。"""
        for u in self.graph:
            self.flow[u] = {}
            for v in self.graph[u]:
                self.flow[u][v] = 0
                # 确保反向边的流量字段存在，即使原始图中没有这条边
                if v not in self.flow:
                    self.flow[v] = {}
                if u not in self.flow[v]:
                    self.flow[v][u] = 0

    def ford_fulkerson(self, source, sink):
        """
        使用Ford-Fulkerson算法计算从source到sink的最大流。
        :param source: 源点
        :param sink: 汇点
        :return: 最大流值
        """
        max_flow = 0
        parent = {} # 用于在DFS中记录路径
        
        while self._dfs(source, sink, parent):
            # 找到一条增广路径，计算瓶颈容量
            path_flow = float('inf')
            v = sink
            while v != source:
                u = parent[v]
                # 瓶颈容量是路径上残量容量的最小值
                residual_capacity = self._get_residual_capacity(u, v)
                path_flow = min(path_flow, residual_capacity)
                v = u
            
            # 沿路径更新流量
            v = sink
            while v != source:
                u = parent[v]
                # 增加正向边流量
                self.flow[u][v] += path_flow
                # 减少反向边流量（等价于增加反向边的残量容量）
                self.flow[v][u] -= path_flow
                v = u
            
            max_flow += path_flow
            parent.clear() # 清空路径记录，准备下一次DFS
        
        return max_flow

    def _dfs(self, source, sink, parent):
        """
        深度优先搜索寻找一条从source到sink的增广路径（在残量网络中）。
        :return: 是否找到路径
        """
        visited = set()
        stack = [source]
        visited.add(source)
        
        while stack:
            u = stack.pop()
            # 遍历所有邻接节点（包括正向和反向边）
            for v in self.graph.get(u, {}):
                # 检查正向边的残量容量
                residual = self._get_residual_capacity(u, v)
                if v not in visited and residual > 0:
                    parent[v] = u
                    if v == sink:
                        return True # 找到增广路径
                    visited.add(v)
                    stack.append(v)
            # 注意：为了简化，这个DFS没有显式遍历所有可能的反向边。
            # 实际上，我们的残量网络是通过`_get_residual_capacity`函数动态计算的，
            # 它已经考虑了原始图和当前流，隐含了反向边的概念。
        return False

    def _get_residual_capacity(self, u, v):
        """计算边(u, v)在残量网络中的容量。"""
        # 原始图的容量（如果存在）
        original_capacity = self.graph.get(u, {}).get(v, 0)
        # 当前流的流量
        current_flow = self.flow.get(u, {}).get(v, 0)
        # 残量容量 = 原始容量 - 当前流
        return original_capacity - current_flow

# 使用示例
if __name__ == "__main__":
    # 定义一个示例网络图（邻接表）
    # s -> A (10), s -> B (5)
    # A -> B (15), A -> t (10)
    # B -> t (10)
    graph = {
        's': {'A': 10, 'B': 5},
        'A': {'B': 15, 't': 10},
        'B': {'t': 10},
        't': {} # 汇点没有出边
    }
    
    solver = MaxFlow(graph)
    source = 's'
    sink = 't'
    max_flow_value = solver.ford_fulkerson(source, sink)
    
    print(f"从 {source} 到 {sink} 的最大流值为: {max_flow_value}")
    # 输出应为: 从 s 到 t 的最大流值为: 15
    # 解释：路径1: s->A->t (流量10)，路径2: s->B->t (流量5)，总流量15。
    # 注意：虽然A->B的容量是15，但s->A只有10，所以无法充分利用。