网络流题选

P2766

【问题分析】
第一问是 LIS 问题，动态规划求解，第二问和第三问用网络最大流解决。
【建模方法】
首先动态规划求出F[i]，表示以第i位为开头的最长上升序列的长度，求出最长上升序列长度K。
1、把序列每位i拆成两个点<i.a>和<i.b>，从<i.a>到<i.b>连接一条容量为1的有向边。
2、建立附加源S和汇T，如果序列第i位有F[i]=K，从S到<i.a>连接一条容量为1的有向边。
3、如果F[i]=1，从<i.b>到T连接一条容量为1的有向边。
4、如果j>i且A[i] < A[j]且F[j]+1=F[i]，从<i.b>到<j.a>连接一条容量为1的有向边。
求网络最大流，就是第二问的结果。把边(<1.a>,<1.b>)(<N.a>,<N.b>)(S,<1.a>)(<N.b>,T)这四条边的容量修改为无穷大，再求一次网络最大流，就是第三问结果。
【建模分析】
上述建模方法是应用了一种分层图的思想，把图每个顶点i按照F[i]的不同分为了若干层，这样图中从S出发到T的任何一条路径都是一个满足条件的最长上升子序列。

由于序列中每个点要不可重复地取出，需要把每个点拆分成两个点。单位网络的最大流就是增广路的条数，所以最大流量就是第二问结果。

第三问特殊地要求x1和xn可以重复使用，只需取消这两个点相关边的流量限制，求网络最大流即可

需要注意的是必须拆点。

P2764

考虑到本质上是做若干匹配，原图上选择一条边等于把两个点的路径合并，总路径数减 \(1\)，所以说直接变成了二分图最大匹配问题，直接匈牙利或者网络流跑都可以。然后又就做完了。

P4313

把每一个人视作一个点 \(i\)。

将 \(S\) 连向这个点，流量为 \(art\)。

将这个点连向 \(T\)，流量为 \(science\)。

新建点，将SS连向这个点，长度为同时选文可获得的收益，并向相邻的那几个点中的每一个点连一条长度为infinf的边。

新建点，将这个点连向TT，长度为同时选理可获得的收益，从相邻的那几个点中的每一个点向新建的点连一条长度为infinf的边。