Snack
[ARC125E] Snack 题解
题目链接 点击打开链接 题目解法 这题看起来很 \(flow\),不难想到边数 \(nm\) 的建图方法: 具体来说,边为 \((S,i,c_i)(i\in [1,m])\),\((i,j,b_i)(i\in [1,m],\;j\in [1,n])\),\((j,T,a_i)(j\in [1,n]\ ......
[ARC125E] Snack
[ARC125E] Snack 经典啊,经典。 很容易看出网络流模型:每个人连一个限制 \(c_i\),每种糖果拆点限流 \(a_i\),然后每个人向每个糖果连边,最大流就是答案。 考虑转成最小割,我们相当于选出两个集合 \(S \subseteq [1,n], T \subseteq [1,m]\ ......
[ARC125E] Snack 题解
不难发现一个较简单的网络流模型: 源点向所有糖果 $i$ 连 $a_i$ 的容量; 所有糖果向所有人 $i$ 连 $b_i$ 的容量; 所有人 $i$ 向汇点连 $c_i$ 的容量。 但第二步中建出的边数达到了惊人的 $O(nm)$,显然过不去。 考虑优化。从最大流角度优化较困难,由于最大流等价于最 ......
AtCoder Regular Contest 125 E Snack
洛谷传送门 AtCoder 传送门 很棒的 flow 题,考虑建二分图。 源点向每种零食连边权为 $a_i$ 的边,每种零食向每个孩子连边权为 $b_j$ 的边,每个孩子向汇点连边权为 $c_j$ 的边,这个图的最大流就是答案。 直接跑最大流肯定 T,考虑最大流等价于求这个图的最小割,因此转而求最小 ......