先二分答案，构建一副新的图。将原图中每个边拆成两条有向边，新的图只保留边权小于答案的边。则问题转化为判断一幅图是否存在欧拉回路，其中边有的有向，有的无向。

根据欧拉回路的性质，一幅有向图有欧拉回路当且仅当每个点度数为偶数。所以可以用网络流来判断是否有欧拉回路。建立超级源，汇点 $s,t$。对于每个边，建立一个新点。$s$ 往新点流容量为 1 的边，代表这条边产生大小为 ...

对每一天，建立一个点 $i$。点 $i$ 往 $i + 1$ 流容量为 $-a_{i+1}$ ，费用为 0 的边，表示下一天至少需要这么多人。 对于每一种志愿者，将 $t_i + 1$ 与 $s_i$ 连容量为 $+\infty$，费用 $c_i$ 的边。 最后从第一天对应的点往最后一天对应的点跑最小费用最大流即可。

对每一天，建立两个点 $d_i, e_i$。分别表示早上和晚上。建立 $s$ 为超级源点，$t$ 为超级汇点。

• 每一天需要 $n_i$ 个毛巾。也会产生 $n_i$ 个脏毛巾。所以 $s$ 往 $e_i$ 连容量为 $n_i$，价值为 0 的边。 $d_i$ 往 $t$ 连容量为 $n_i$，价值为 0 的边。
• 每一天的脏毛巾可以留给...

杜教筛是一种快速求出积性函数前缀和的算法。

Part 1 前置知识

• 积型函数
  • 若对于任意满足 $x \perp y$ 的 $x,y$，都有 $f(x)f(y)=f(xy)$，则 $f(x)$ 是积性函数。
• ...

建立超级源点 $s$ 和超级汇点 $t$。对于仓库 $i$，首先将 $i$ 与相邻的两个仓库连容量为 $+\infty$，价值为 $1$ 的边。如果 $a_i - \sum_{i=1}^{n}\frac{a_i}{n} > 0$，则 $i$ 需要移走多余的货物。所以源点往 $i$ 连容量为 $a_i - \sum_{i=1}^{n}\frac{a_i}{n}$，价值为 $0$ 的...

建立超级源点 $s$ 和超级汇点 $t$。对每个顾客和猪圈建一个点。对于顾客 $i$，将 $i$ 与汇点连容量为 $b_i$ 的边。对于🐖圈 $i$，将源点与 $i$ 连容量为 $p_i$ 的边。对于每个 $k_i$，考虑其中的每个猪圈。如果猪圈没有其他顾客来过，则该猪圈往顾客连容量为 $+\infty$ 的边。否则上一次来过的顾客往现在的顾客连容量为 $+\infty$ 的边。最后跑...

• 小鸥定理与扩展小鸥定理
  • 小鸥定理：$a^{phi(m)} \equiv 1 \pmod m$，其中 $\gcd(m,a) = 1$
  • 扩展小鸥定理：$a^b \equiv a^{\varphi(m) + b \mod \varphi(m)} \pmod m$
  • 扩鸥定理应用： ...

一道关于 Legendre 符号的推式子好题。 首先引入 Legendre 符号。定义 Legendre 符号 $\dbinom{a}{p} = \begin{cases} 0 & \gcd (a,p) \ne 1 \ 1 & \gcd (a,p) = 1 \land ((\exists x \in \text Z) x^2 \equiv a \pmod p) \ -1...