最多不相交路径
??? 最长上升子序列是一个经典问题，可以用O(n^2)的dp解决。给出一个串，求出最长上升子序列的长度为多少？假设长度为s，现在问题是，有多少个长度为s的上升子序列，满足每个子序列所包含的元素均不相同(即一个数只能选一次)。
??? 建模：
??? 第一问直接用dp求解，dp[i]表示以i为结尾的最长递增子序列的长度，最后取dp[1~n]的最大值，即为s。
??? 第二问可以利用上一问求出来的dp数组，用网络流求解。
??? 1. 拆点，将每个点拆成两点，容量为1，保证每个点只取一次。
??? 2. 增加源点s和汇点t，s和dp[i]=1的点相连，dp[i]=s的点和t相连，容量均为INF。
??? 3. 对于两点i和j(j<i)，如果满足条件：a[j]<a[i]&&dp[j]+1=dp[i]，添加有向边(j,i)，容量为INF。
??? 这样，保证从s到t的每一条路都是一条最长递增子序列，最大流即为答案。
?? 例：HDU3998
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int INF = 0x7fffffff;const int maxv = 2000;const int maxe = maxv*maxv*2;int n,s;int a[maxv];int dp[maxv];int source,sink;//struct Edge{ int v; int next; int flow;};Edge e[maxe];int head[maxv],edgeNum;int now[maxv],d[maxv],vh[maxv],pre[maxv],preh[maxv];void addEdge(int a,int b,int c){ e[edgeNum].v = b; e[edgeNum].flow = c; e[edgeNum].next = head[a]; head[a] = edgeNum++; e[edgeNum].v = a; e[edgeNum].flow = 0; e[edgeNum].next = head[b]; head[b] = edgeNum++;}void Init(){ edgeNum = 0; memset(head,-1,sizeof(head)); memset(d,0,sizeof(d));}int sap(int s,int t,int n) //源点，汇点，结点总数{ int i,x,y; int f,ans = 0; for(i = 0; i < n; i++) now[i] = head[i]; vh[0] = n; x = s; while(d[s] < n) { for(i = now[x]; i != -1; i = e[i].next) if(e[i].flow > 0 && d[y=e[i].v] + 1 == d[x]) break; if(i != -1) { now[x] = preh[y] = i; pre[y] = x; if((x=y) == t) { for(f = INF,i=t; i != s; i = pre[i]) if(e[preh[i]].flow < f) f = e[preh[i]].flow; ans += f; do { e[preh[x]].flow -= f; e[preh[x]^1].flow += f; x = pre[x]; }while(x!=s); } } else { if(!--vh[d[x]]) break; d[x] = n; for(i=now[x]=head[x]; i != -1; i = e[i].next) { if(e[i].flow > 0 && d[x] > d[e[i].v] + 1) { now[x] = i; d[x] = d[e[i].v] + 1; } } ++vh[d[x]]; if(x != s) x = pre[x]; } } return ans;}//void build(){ int i,j; Init(); source = 0; sink = 2*n+1; for(i = 1; i <= n; i++) addEdge(i,i+n,1); for(i = 1; i <= n; i++) { if(dp[i]==1) addEdge(source,i,INF); if(dp[i]==s) addEdge(i+n,sink,INF); } for(i = 1; i <= n; i++) { for(j = 1; j < i; j++) { if(a[j] < a[i] && dp[j]+1 == dp[i]) addEdge(j+n,i,INF); } }}int main(){ int i,j; while(scanf("%d",&n)!=EOF) { s = -1; for(i = 1; i <= n; i++) scanf("%d",&a[i]); for(i = 1; i <= n; i++) dp[i] = 1; for(i = 1; i <= n; i++) { for(j = 1; j < i; j++) { if(a[j] < a[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1; } } for(i = 1; i <= n; i++) { if(s < dp[i]) s = dp[i]; } printf("%d\n",s); build(); printf("%d\n",sap(source,sink,sink+1)); } return 0;}?
?