很久以前，看到家乡洪水肆虐，大禹决心要把洪水引到大海里，因此带领众人修建立了一套水沟系统。他们在每条水沟都装了阀门来控制水的流量。他们设计了每条水沟每分钟的排水量，以及水沟的整体布局。洪水从池塘流出，最后汇入大海。请确定洪水从家乡流入大海的最大流量。输入格式: 第一行包含两个整数N和M，分别表示水沟数量和水沟的交叉点数量，其中交叉点1代表家乡，交叉点M是大海。后面N行，每行三个整数，s，e，c，其中s，e表示交叉点且水从s流向e，最大流量是c（0到10000之间）。输出格式: 输出排出水的最大流量。输入样例: 在这里给出一组输入。例如： 5 4 1 2 40 1 4 20 2 4 20 2 3 30 输出样例: 在这里给出相应的输出。例如： 40

以下是Python代码实现，使用网络流模板库来实现Edmonds-Karp算法，时间复杂度为O(V*E^2)，其中V为节点数，E为边数：

from collections import deque
from typing import List, Tuple
from collections import defaultdict


class Edge:
    def __init__(self, to, cap, rev):
        self.to = to
        self.cap = cap
        self.rev = rev


class MaxFlow:
    def __init__(self, n: int):
        self.n = n
        self.edges = defaultdict(list)
        self.level = [0] * n
        self.iter = [0] * n

    def add_edge(self, frm: int, to: int, cap: int):
        self.edges[frm].append(Edge(to, cap, len(self.edges[to])))
        self.edges[to].append(Edge(frm, 0, len(self.edges[frm]) - 1))

    def bfs(self, s: int):
        self.level = [-1] * self.n
        q = deque()
        self.level[s] = 0
        q.append(s)

        while q:
            v = q.popleft()
            for e in self.edges[v]:
                if e.cap > 0 and self.level[e.to] < 0:
                    self.level[e.to] = self.level[v] + 1
                    q.append(e.to)

    def dfs(self, v: int, t: int, f: int):
        if v == t:
            return f

        for i in range(self.iter[v], len(self.edges[v])):
            e = self.edges[v][i]
            if e.cap > 0 and self.level[v] < self.level[e.to]:
                d = self.dfs(e.to, t, min(f, e.cap))
                if d > 0:
                    e.cap -= d
                    self.edges[e.to][e.rev].cap += d
                    return d

            self.iter[v] += 1

        return 0

    def max_flow(self, s: int, t: int) -> int:
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                break
            self.iter = [0] * self.n
            while True:
                f = self.dfs(s, t, float('inf'))
                if f == 0:
                    break
                flow += f

        return flow


def solve(n: int, m: int, edges: List[Tuple[int, int, int]]) -> int:
    s = 0
    t = m - 1
    g = MaxFlow(m)
    for u, v, w in edges:
        g.add_edge(u - 1, v - 1, w)
        g.add_edge(v - 1, u - 1, 0)

    return g.max_flow(s, t)


if __name__ == '__main__':
    n, m = map(int, input().split())
    edges = []
    for i in range(n):
        u, v, w = map(int, input().split())
        edges.append((u, v, w))
    print(solve(n, m, edges))

输入样例：

5 4
1 2 40
1 4 20
2 4 20
2 3 30

输出样例：

40