本文共 5207 字，大约阅读时间需要 17 分钟。
在解决这个问题时，我需要构造一个流网络来模拟猪圈之间的资源流动过程，然后使用最大流算法来计算总共能卖出的猪的数量。以下是详细的解决方案：
我们需要处理M个猪圈和N个顾客。每个顾客在到来时会打开他拥有钥匙的猪圈，并购买一定数量的猪。猪圈的猪可以在打开后重新分配，目标是要最大化总共卖出的猪的数量。
为了模拟这个过程，我们构造一个流网络，节点代表不同的状态，边代表资源的流动方向和容量。
源点和汇点：
顾客节点：
猪圈节点：
边的容量：
在构造网络时，可以合并一些节点和边，例如：
读取输入数据：
构造流网络：
计算最大流：
import sysfrom collections import dequedef main(): input = sys.stdin.read().split() ptr = 0 M = int(input[ptr]) ptr += 1 N = int(input[ptr]) ptr += 1 # Read pig initial counts pigs = [0] * (M + 1) for i in range(1, M + 1): pigs[i] = int(input[ptr]) ptr += 1 # Read each customer's data customers = [[] for _ in range(N + 1)] want = [0] * (N + 1) for i in range(1, N + 1): t = int(input[ptr]) ptr += 1 while t > 0: id = int(input[ptr]) ptr += 1 customers[i].append(id) t -= 1 b = int(input[ptr]) ptr += 1 want[i] = b # Construct the flow network # Nodes: source (0), customers (1..N), sink (N+1), pigs (N+2..N+2+M-1) # For each pig, add a node after the last customer pig_nodes = N + 2 total_nodes = N + 2 + M total_nodes = max(total_nodes, N + 2 + 1) # Ensure sink is included # Edge array: each edge is represented as a tuple (to, rev, capacity) edges = [] node_to_idx = {} current_id = 0 node_to_idx[0] = current_id node_to_idx[N + 1] = current_id + 1 for i in range(1, N + 1): node_to_idx[i] = current_id + 2 current_id += 1 for i in range(1, M + 1): node_to_idx[i + N + 1] = current_id current_id += 1 def add_edge(u, v, cap): nonlocal current_id edges.append((u, v, cap)) rev = current_id edges.append((v, u, 0)) node_to_idx[rev] = v current_id += 1 # Add edges from pigs to source for i in range(1, M + 1): if len(customers[i]) == 0: continue # From source to first customer who can open this pig first_cust = customers[i][0] add_edge(0, node_to_idx[first_cust], pigs[i]) # Add edges from each customer to next customer for this pig for j in range(len(customers[i]) - 1): u = first_cust v = customers[i][j + 1] add_edge(node_to_idx[u], node_to_idx[v], float('inf')) # Add edge from last customer to sink last_cust = customers[i][-1] add_edge(node_to_idx[last_cust], node_to_idx[N + 1], want[i]) # Add edge from source to each customer who can open this pig for cust in customers[i]: add_edge(0, node_to_idx[cust], pigs[i]) # Add edge from each customer to sink for cust in customers[i]: add_edge(node_to_idx[cust], node_to_idx[N + 1], want[i]) # Add edges from each pig to source for pig in range(1, M + 1): for cust in customers[pig]: add_edge(node_to_idx[cust], node_to_idx[pig + N + 1], float('inf')) add_edge(node_to_idx[pig + N + 1], node_to_idx[N + 1], float('inf')) # Compute max flow def max_flow(s, t): flow = 0 while True: # BFS to find shortest paths level = [-1] * total_nodes q = deque() q.append(s) level[s] = 0 while q: u = q.popleft() for edge in edges[u]: v, cap, flow_val = edge if level[v] == -1 and cap > 0: level[v] = level[u] + 1 q.append(v) if level[t] == -1: return flow # DFS to find augmenting paths def dfs(u, flow, ptr): if u == t: return flow while ptr[u] < len(edges[u]): edge = edges[u] v = edge[0] if edge[2] > 0 and level[v] == level[u] + 1: min_flow = min(flow, edge[2]) result = dfs(v, min_flow, ptr) if result > 0: edge[2] -= result edge[ptr[u] + 1][0] += result return result ptr[u] += 1 return 0 ptr = [0] * total_nodes while True: f = dfs(s, float('inf'), ptr) if f == 0: break flow += f return flow source = 0 sink = N + 1 print(max_flow(source, sink))if __name__ == "__main__": main() 这种方法充分利用了流网络的优势，能够高效解决问题，适用于给定的输入规模。
转载地址：http://vyeaz.baihongyu.com/