「网络流24题」最长递增子序列问题

2014年12月27日6,4735

题意有些奇怪

任务(2)是取出。。。且题中递增是非严格递增

我的代码任务3若能取出无限多的序列,则输出-1

输入

4

1 3 2 4

输出

3 1 2

样例2

输入

4

3 6 2 5

输出

2 2 -1

搬运byvoid神犇题解

「问题分析」

第一问是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可以重复使用,只需取消这两个点相关边的流量限制,求网络最大流即可。

 

avatar
4 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
3 Comment authors
Sigma_Poethzwer黑人桑蔡伟斌 Recent comment authors
  Subscribe  
提醒
Sigma_Poet
Sigma_Poet

黄学长,好像你题解里面说的和你连边的方式不太一样。

黑人桑
黑人桑

应将solve2()中第二个添边部分中将i+n和j所连得边的流量修改为1而不是inf

蔡伟斌
蔡伟斌

然而对于
4
3 6 2 5
这个数据并没有输出正解
正解:
2
2
3
程序输出:
2
2
-1

Z8811062

改了一句(不然80分)
if(tmp>=inf) printf(“%dn”, n); // puts(“-1”);