题意
给定一个有向无环图，每条边有权重 \(w_i\)，给每个点分配权值 \(a_i\)，使每个点的权值大于其所有出点。设每条边的权值为 \(a_{x_i}-a_{b_i}\)。输出一种分配方案，使得边的权重 \(×\) 权值的和最小。
题解
将边权拆成点权，则对于每条边 \((x,y,z)\)，\(w_{x_i}+=z,w_{y_i}-=z\)。问题转化为分配点权使 \(a_i×w_i\) 最小。
有一个性质：\(a_i∈[0,n-1]\)。易证。
由于 \(n\) 很小，可以考虑将每个点拆为 \(n\) 个点，分别表示其 \(a_i\)。在此基础上跑网络流。
由题解得一种很好的建图方法，即将每个点的拆点首尾相连形成一条链，链的头尾分别与 \(S,T\) 相连。问题转化为最小割，割断一条边即为取对应的权值。另外还有 \(a_i\) 之间的限制条件，则对于 \((x,y)\)，连 \((y_j,x_{j+1},INF),j∈[0,n-1]\)。则若取了 \(x_i\)，就不能取 \(y_j,j≥i\)。
流量不能有负值，平移即可。