2.太空飞行计划问题 最大权闭合图 以后研究
4.魔术球问题 转化为最小路径覆盖
5.圆桌问题
建立二分图,每个单位为X集合中的顶点,每个餐桌为Y集合中的顶点,增设附加源S和汇T。
1、从S向每个Xi顶点连接一条容量为该单位人数的有向边。
2、从每个Yi顶点向T连接一条容量为该餐桌容量的有向边。
3、X集合中每个顶点向Y集合中每个顶点连接一条容量为1的有向边。
求网络最大流,如果最大流量等于所有单位人数之和,则存在解,否则无解。对于每个单位,从X集合对应点出发的所有满流边指向的Y集合的顶点就是该单位人员的安排情况(一个可行解)。
8.最长递增子序列问题
«问题描述:
给定正整数序列nxx,,1。
(1)计算其最长递增子序列的长度s。
(2)计算从给定的序列中最多可取出多少个长度为s的递增子序列。
(3)如果允许在取出的序列中多次使用x1和xn,则从给定序列中最多可取出多少个长度为s的递增子序列。
【问题分析】
第一问时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可以重复使用,只需取消这两个点相关边的流量限制,求网络最大流即可。
11.航空路线问题
就是那个模板题,拆点就可以