首页 > 代码库 > [luoguP2766] 最长递增子序列问题（最大流）
[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可以重复使用，只需取消这两个点相关边的流量限制，求网络最大流即可。
还有这个题题意有些问题，不是递增，是不递减。
还有我这个题没有拆点在洛谷和codevs上都过了，究竟需不需要拆点啊。。
——代码（木有拆点）
1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define N 1010 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 { 16 int x = 0, f = 1; 17 char ch = getchar(); 18 for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1; 19 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘; 20 return x * f; 21 } 22 23 inline void add(int x, int y, int z) 24 { 25 to[cnt] = y; 26 val[cnt] = z; 27 next[cnt] = head[x]; 28 head[x] = cnt++; 29 } 30 31 inline bool bfs() 32 { 33 int i, u, v; 34 std::queue <int> q; 35 memset(dis, -1, sizeof(dis)); 36 q.push(s); 37 dis[s] = 0; 38 while(!q.empty()) 39 { 40 u = q.front(), q.pop(); 41 for(i = head[u]; i ^ -1; i = next[i]) 42 { 43 v = to[i]; 44 if(val[i] && dis[v] == -1) 45 { 46 dis[v] = dis[u] + 1; 47 if(v == t) return 1; 48 q.push(v); 49 } 50 } 51 } 52 return 0; 53 } 54 55 inline int dfs(int u, int maxflow) 56 { 57 if(u == t) return maxflow; 58 int i, v, d, ret = 0; 59 for(i = cur[u]; i ^ -1; i = next[i]) 60 { 61 v = to[i]; 62 if(val[i] && dis[v] == dis[u] + 1) 63 { 64 d = dfs(v, min(val[i], maxflow)); 65 ret += d; 66 cur[u] = i; 67 val[i] -= d; 68 val[i ^ 1] += d; 69 if(ret == maxflow) return ret; 70 } 71 } 72 return ret; 73 } 74 75 inline void clear() 76 { 77 int i, j; 78 sum = cnt = 0; 79 memset(head, -1, sizeof(head)); 80 for(i = 1; i <= n; i++) 81 { 82 if(f[i] == 1) add(s, i, 1), add(i, s, 0); 83 if(f[i] == ans) add(i, t, 1), add(t, i, 0); 84 } 85 for(i = 1; i <= n; i++) 86 for(j = 1; j < i; j++) 87 if(a[j] <= a[i] && f[j] + 1 == f[i]) 88 add(j, i, 1), add(i, j, 0); 89 } 90 91 int main() 92 { 93 int i, j, x; 94 n = read(); 95 s = 0, t = n + 1; 96 for(i = 1; i <= n; i++) 97 { 98 a[i] = read(); 99 x = 0;100 for(j = 1; j < i; j++)101 if(a[j] <= a[i])102 x = max(x, f[j]);103 f[i] = x + 1;104 ans = max(ans, f[i]);105 }106 printf("%d\n", ans);107 clear();108 while(bfs())109 {110 for(i = s; i <= t; i++) cur[i] = head[i];111 sum += dfs(s, 1e9);112 }113 printf("%d\n", sum);114 clear();115 add(s, 1, 1e9), add(1, s, 0);116 if(f[n] == ans) add(n, t, 1e9), add(t, n, 0);117 while(bfs())118 {119 for(i = s; i <= t; i++) cur[i] = head[i];120 sum += dfs(s, 1e9);121 }122 printf("%d\n", sum);123 return 0;124 }
[luoguP2766] 最长递增子序列问题（最大流）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。