网络流 之 P2766 最长不下降子序列问题
题目描述
«问题描述：
给定正整数序列x1,...,xn 。
（1）计算其最长不下降子序列的长度s。
（2）计算从给定的序列中最多可取出多少个长度为s的不下降子序列。
（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长度为s的不下降子序列。
«编程任务：
设计有效算法完成（1）（2）（3）提出的计算任务。
输入输出格式
输入格式：
第1 行有1个正整数n，表示给定序列的长度。接下来的1 行有n个正整数n:x1, ..., xn。
输出格式：
第1 行是最长不下降子序列的长度s。第2行是可取出的长度为s 的不下降子序列个数。第3行是允许在取出的序列中多次使用x1和xn时可取出的长度为s 的不下降子序列个数。
输入输出样例
说明
500n≤500
最长不下降子序列
这个题目第一问显然是LIS
第二问和第三问就转化成最大流。
转化过程（理解了好久）
第二问：
建图，先求出f数组，f[i]表示到第i为的最长的不下降子序列，
然后因为第二问每一个数只能用一次，所以就把一个点拆成一个入点一个出点。
建图就是让f[i]==1的和s连在一起，f[i]==ans的和t连在一起，然后中间如果有
a[i]>=a[j]&&i>j&&f[i]=f[j]+1 这样的话就把 j 的出点和 i 的入点连在一起，这个就是建图过程。
接下来说说为什么这么建图，
首先只考虑第二问，因为每一个点只能用一次，所以就把点拆开，并且权值为1 ,然后因为只有f[i]==1
才会和s点相连，设f[i]==1的个数为x，所以这个就说明最多只能有x个答案，在这个基础上再看有没有从这个
点出发可以到达f[i]==ans的。
接下来说说为什么会 a[i]>=a[j]&&i>j&&f[i]=f[j]+1 这个j的出点和i的入点连在一起。
这个必须是这样子写的，因为只有这个样子到f[i]==ans 的过程中把中间的数字标记一次，不让别的再跑了。
例如说样例： 3 6 2 5 这个ans=2 第二问答案有两组就是 3 6 和 2 5，
3和2都与源点连起来了，6和5 都和汇点连起来了，3也会和6 5 连起来，2就只会和6 连起来，
然后这个答案可以是3 5 或者2 6 和2 5 ，很显然后面的才是最大流。
然后第三问 首先你要看清楚题目，题目说的只是x1和xn可以用无数多次，
所以这个就只要改成 s 到1 和1到n+1 和 n到 n+n if(f[n]==ans) n到 t 这些边改成无数次然后就再跑一次。
因为f[i]==1所以从s到1很有可能会跑很多次，所以，这个既然x1可以用无数多次，则要设s到1和1到1+n为无数多次
如果f[n]!=ans 则说明这个点不会和t连在一起，所以就不能连n到t，但是n到n+n可以连无数多次，不过好像没什么用。
因为n是最后一个
#include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #include <queue> #include <vector> #include <string> #define inf 0x3f3f3f3f using namespace std; const int maxn = 1e5; int s, t; struct node { int from, to, cap, flow; node(int from=0,int to=0,int cap=0,int flow=0):from(from),to(to),cap(cap),flow(flow){} }; vector<node>e; vector<int>G[maxn]; void add(int u,int v,int w) { e.push_back(node(u, v, w, 0)); e.push_back(node(v, u, 0, 0)); int m = e.size(); G[u].push_back(m - 2); G[v].push_back(m - 1); } int a[maxn], dp[maxn]; int level[maxn], iter[maxn]; void bfs(int s) { memset(level, -1, sizeof(level)); level[s] = 0; queue<int>que; que.push(s); while(!que.empty()) { int u = que.front(); que.pop(); for(int i=0;i<G[u].size();i++) { node &now = e[G[u][i]]; if(now.cap>now.flow&&level[now.to]<0) { level[now.to] = level[u] + 1; que.push(now.to); } } } } int dfs(int u,int v,int f) { if (u == v) return f; for(int &i=iter[u];i<G[u].size();i++) { node &now = e[G[u][i]]; if(now.cap>now.flow&&level[now.to]>level[u]) { int d = dfs(now.to, v, min(f, now.cap - now.flow)); if(d>0) { now.flow += d; e[G[u][i] ^ 1].flow -= d; return d; } } } return 0; } int dinic() { int flow = 0; while(1) { bfs(s); if (level[t] < 0) return flow; memset(iter, 0, sizeof(iter)); int f; while ((f = dfs(s, t, inf)) > 0) flow += f; } } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; s = 0, t = 2 * n + 1; int res = 0; for(int i=1;i<=n;i++) { dp[i] = 1; for(int j=1;j<i;j++) { if (a[j] <= a[i]) dp[i] = max(dp[i], dp[j] + 1); } res = max(res, dp[i]); } printf("%d ", res); for (int i = 1; i <= n; i++) add(i, i + n, 1); for (int i = 1; i <= n; i++) if (dp[i] == 1) add(s, i, 1); for (int i = 1; i <= n; i++) if (dp[i] == res) add(i+n, t, 1); for(int i=1;i<=n;i++) { for(int j=1;j<i;j++) { if (a[i] >= a[j] && dp[i] == dp[j] + 1) add(j + n, i, 1); } } int ans = dinic(); printf("%d ", ans); add(s, 1, inf); add(1, 1 + n, inf); if (dp[n] == res) add(n, t, inf),add(n, n + n, inf); int ech = dinic(); printf("%d ", ech+ans); return 0; }