本文共 5010 字，大约阅读时间需要 16 分钟。

为了解决牛避雨的问题，我们需要构建一个图模型，其中每个点代表一个顶点，具有当前牛的数量和雨棚的容量。牛们可以从多个源点出发，移动到多个汇点，目标是找到最短的时间使所有牛都能避雨。

模型构建

代码实现

import sys
from collections import deque
def main():
    n = int(sys.stdin.readline())
    m = int(sys.stdin.readline())
    cow = [0] * (n + 1)
    shelter = [0] * (n + 1)
    num_cows = 0
    sh = 0
    for i in range(1, n + 1):
        a, b = map(int, sys.stdin.readline().split())
        cow[i] = a
        shelter[i] = b
        num_cows += a
    INF = 1 << 60
    max_flow = 0
    level = [0] * (2 * n + 2)
    vis = [False] * (2 * n + 2)
    head = [-1] * (2 * n + 2)
    size = 2 * n + 2
    def bfs(s, t):
        queue = deque()
        vis[s] = True
        level[s] = 0
        queue.append(s)
        while queue:
            u = queue.popleft()
            if u == t:
                return True
            for i in range(head[u], -1, -1):
                v = e[i][0]
                if not vis[v]:
                    vis[v] = True
                    level[v] = level[u] + 1
                    queue.append(v)
                    if v == t:
                        return True
            head[u] = -1
    def dfs(u, flow):
        if u == t:
            return flow
        while head[u] != -1:
            v = e[head[u]][0]
            if level[v] == level[u] + 1 and e[head[u]][2] > 0:
                min_flow = min(flow, e[head[u]][2])
                res = dfs(v, min_flow)
                if res > 0:
                    e[head[u]][2] -= res
                    e[head[u] + 1][2] += res
                    return res
            head[u] = e[head[u] + 1][0]
        return 0
    e = [[] for _ in range(size * 2)]
    head = [-1] * size
    def add_edge(u, v, cap):
        e[u].append((v, cap))
        e[v].append((u, 0))
    def bfs_level():
        queue = deque()
        vis = [False] * size
        level = [0] * size
        queue.append(0)
        vis[0] = True
        while queue:
            u = queue.popleft()
            for (v, _) in e[u]:
                if not vis[v]:
                    vis[v] = True
                    level[v] = level[u] + 1
                    queue.append(v)
                    if v == t:
                        return True
        return False
    def dfs_flow(u, flow):
        if u == t:
            return flow
        while head[u] != -1:
            v = e[head[u]][0]
            if level[v] == level[u] + 1 and e[head[u]][2] > 0:
                min_flow = min(flow, e[head[u]][2])
                res = dfs_flow(v, min_flow)
                if res > 0:
                    e[head[u]][2] -= res
                    e[head[u] + 1][2] += res
                    return res
            head[u] = e[head[u] + 1][0]
        return 0
    t = n + 1
    for i in range(1, n + 1):
        add_edge(0, i, cow[i])
        add_edge(i, t, shelter[i])
        for j in range(1, n + 1):
            if shelter[i] > 0 and shelter[j] > 0:
                add_edge(i, j, INF)
                add_edge(j, i, INF)
    while True:
        level = [0] * size
        vis = [False] * size
        q = deque()
        q.append(0)
        vis[0] = True
        while q:
            u = q.popleft()
            if u == t:
                break
            for (v, cap) in e[u]:
                if not vis[v]:
                    vis[v] = True
                    level[v] = level[u] + 1
                    q.append(v)
        if vis[t]:
            break
        head = [-1] * size
        while True:
            u = t
            flow = 0
            while u != 0:
                v = e[head[u]][0]
                if level[v] == level[u] + 1 and e[head[u]][2] > 0:
                    min_flow = min(flow, e[head[u]][2])
                    res = dfs_flow(v, min_flow)
                    if res > 0:
                        flow += res
                        e[head[u]][2] -= res
                        e[head[u] + 1][2] += res
                        u = v
                    else:
                        break
                head[u] = e[head[u] + 1][0]
                u = e[head[u]][0]
            if flow > max_flow:
                max_flow = flow
            level = [0] * size
            vis = [False] * size
            q = deque()
            q.append(0)
            vis[0] = True
            while q:
                u = q.popleft()
                for (v, cap) in e[u]:
                    if not vis[v]:
                        vis[v] = True
                        level[v] = level[u] + 1
                        q.append(v)
                if u == t:
                    break
        if max_flow == num_cows:
            break
    print(max_flow)
if __name__ == "__main__":
    main()

代码解释

通过上述步骤，可以高效地解决牛避雨问题，确保所有牛在最短时间内安全到达。

转载地址：http://pyxfk.baihongyu.com/