洛谷题面
题目大意比较简单,最重要的就是这三种规则了:
1.从梯形的顶至底的 \(m\) 条路径互不相交；
2.从梯形的顶至底的 \(m\) 条路径仅在数字结点处相交；
3.从梯形的顶至底的 \(m\) 条路径允许在数字结点相交或边相交。
考虑网络流,建立源点\(S\)和汇点\(T\),从\(S\)向每个顶层数字连边,每个底层数字也向\(T\)连边
中间的数字,都朝着左下和右下的节点连边
按照网络流的思维方式,我们尝试从其中提取出限制:
1.每条边只能选择一次,每个点只能选一次
2.每条边只能选一次,每个点可以被选无数次
3.每条边能被选无数次,每个点可以被选无数次
对于限制1:把不同点之间的边的流量定为1,对于同一点,拆点,拆成\(i\)和\(i'\),在其中间连流量为1的边,价值为数字大小
对于限制2:把不同点之间的边的流量定为1,对于同一点,拆点,拆成\(i\)和\(i'\),在其中间连流量为正无穷的边,价值为数字大小
对于限制3:把不同点之间的边的流量定为正无穷,对于同一点,拆点,拆成\(i\)和\(i'\),在其中间连流量为正无穷的边,价值为数字大小
然后对于每个建图方法,跑一遍最大费用最大流,就可以求出其答案
标签：拆成,费用,数字,连边,梯形,至底,流量 From： https://www.cnblogs.com/sheepcsy/p/16625714.html