图论杂题

考虑在网络里用一个流量表示人。每个点拆成入点和出点，入和出之间连一条限制流量 $\geq 1$ 的边，然后出点向 $T$ 连流量为 $\infty$ 的边表示一个人可以从这里结束，$S$ 向额外一个辅助点连流量为 $a_i$ 的边，辅助点向入点连费用为 $1$，出点连费用为 $0$ 的边即可。

直接跑最小费用可行流会有问题，因为可能会有环流，所以需要缩点。

什么 b 题。

连边，把每个点的 $in$ 和 $out$ 补成一样的，跑欧拉回路，这样可以把图划分成 $60$ 条链。

枚举平均数之后跑流，发现是每次选一个类似最大子段和的东西。

把每个三角形第一个点确定为 $+5$，第二个点确定为 $+4$ 或 $+5$，这样第三个点至少有两种合法的取值。一个点的邻居数是 $B+2C$。

若图没有完美匹配，可以简单（？？？？）找出

讲题