[luoguP2766] 最长递增子序列问题（最大流）

传送门

题解来自网络流24题：

【问题分析】

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

还有这个题题意有些问题，不是递增，是不递减。

——代码

1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define N 2020 6 #define M 3000001 7 #define max(x, y) ((x) > (y) ? (x) : (y)) 8 #define min(x, y) ((x) < (y) ? (x) : (y)) 9 10 int n, ans, cnt, s, t, sum; 11 int a[N], f[N]; 12 int head[N], to[M], val[M], next[M], dis[N], cur[N]; 13 14 inline int read() 15 22 23 inline void add(int x, int y, int z) 24 30 31 inline bool bfs() 32 50 } 51 } 52 return 0; 53 } 54 55 inline int dfs(int u, int maxflow) 56 71 } 72 return ret; 73 } 74 75 inline void clear() 76 86 for(i = 1; i <= n; i++) 87 for(j = 1; j < i; j++) 88 if(a[j] <= a[i] && f[j] + 1 == f[i]) 89 add(j + n, i, 1), add(i, j + n, 0); 90 } 91 92 int main() 93 107 printf("%d\n", ans); 108 clear(); 109 while(bfs()) 110 114 printf("%d\n", sum); 115 clear(); 116 add(s, 1, 1e9), add(1, s, 0); 117 add(1, 1 + n, 1e9), add(1 + n, 1, 0); 118 if(f[n] == ans) 119 123 while(bfs()) 124 128 printf("%d\n", sum); 129 return 0; 130 }
View Code

上一篇：[luoguP2765] 魔术球问题（最大流—最小不相交路径覆盖）

下一篇：[luoguP2763] 试题库问题（最大流）

---

最大流 网络流