本文共 4860 字，大约阅读时间需要 16 分钟。
为了解决牛避雨的问题，我们需要构建一个图模型，其中每个点代表一个顶点，具有当前牛的数量和雨棚的容量。牛们可以从多个源点出发，移动到多个汇点，目标是找到最短的时间使所有牛都能避雨。
超级源点和超级汇点：
边的容量：
Dinic算法：
import sysfrom collections import dequedef 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/