Educational Codeforces Round 96
G. Yet Another DAG Problem
题意
给定一个有向无环带边权图，要求给每个点赋值 $a$，对边 $u\to v$，要求 $a_u\gt a_v$，且最小化 $\sum_{i=1}^m w_i(a_{u_i}-a_{v_i})$。
题解
首先，假设 $a$ 的取值不连续，不妨设不存在 $a=v$，于是将 $a\gt v$ 的点权值减一，则答案仍然合法，且 $\sum_{i=1}^m w_i(a_{u_i}-a_{v_i})$ 不增。
于是不妨假设 $a$ 的取值必定为连续的一段，于是 $a\le n-1$。
$$ \sum_{i=1}^m w_i(a_{u_i}-a_{v_i})=\sum_{i=1}^n \left(\sum_{u_j=i}w_j-\sum_{v_j=i}w_j\right)a_i=\sum_{i=1}^n c_ia_i $$
于是只需要考虑每个点的最优点权分配即可，考虑构建最小割模型。
首先令 $e_{i,j}$ 表示 $a_i=j$，于是令该边的容量即删除该边的代价为 $jc_i$。记 $b_{i,j}=u_{e_{i,j}}$。
考虑连边 $s\to b_{i,0}\to b_{i,1}\to \cdots\to b_{i,n-1}\to t$，其中 $s\to b_{i,0},b_{i,n-1}\to t$ 边权为 $\inf$。该链上必须选择一条边。
接下来考虑维护 $a_u\gt a_v$ 的约束，于是连边 $b_{v,i}\to b_{u,i+1}$，并将其容量设为 $\inf$。
表示如果选择 $e_{v,i}$，则考虑链 $s\to b_{v,0}\to b_{v,1}\to\cdots\to b_{v,i}\to b_{u,i+1}\to \cdots\to t$。
该链上必须选择一条边，而选择了 $e_{v,i}$ 则不需要考虑 $e_{v,j}(j\lt i)$，于是 $e_{u,j}(j\gt i)$ 必须选择一条。
最后由于部分点 $c_i\le 0$，考虑为图中每条边加上一个偏移量。
由于最小割至少要包含 $n$ 条边，且该模型必须只选择 $n$ 条边，于是不影响正确性。
图中有 $O(n^2)$ 个点，$O(nm)$ 条边，于是时间复杂度为 $O(n^5m)$。
