题意：给出一个n个数字的序列，求最长上升子序列长度，并求出最多可以找出多少个最长上升子序列（每个位置上的数字只能在找出的序列中出现一次）
只能出现一次，还是可以联想到最大流的。而对于一个已经给定了的长度，貌似想控制在网络中的路径长度不太可能。假定每个位置上的当前最长上升子序列的标记为dp(i)。每个流会对应一种物理方案，那么必须是dp(j)=dp(i)+1,(j>i),所以，对于所有的符合条件的i,j，有边(i',j,1)。另外由于是每个数字只可以使用一次，所以肯定对应一条边(i,i',1)，对于所有dp(i)=1的点，对应边(S,i,1),对于所有dp(i)=ans的点，对应边(i',T,1)，这样一来，跑S->T的最大流就可以得出答案。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define INF 0x7fffffff 6 #define maxn 1<<13 7 #define maxm 1<<17 8 using namespace std; 9 int v[maxm],next[maxm],w[maxm]; 10 int first[maxn],d[maxn],work[maxn],q[maxn]; 11 int e,S,T; 12 int dp[maxn],s[maxn]; 13 void init(){ 14 e = 0; 15 memset(first,-1,sizeof(first)); 16 } 17 18 void add_edge(int a,int b,int c){ 19 //printf("add:%d to %d,cap = %d ",a,b,c); 20 v[e] = b;w[e] = c;next[e] = first[a];first[a] = e++; 21 v[e] = a;w[e] = 0;next[e] = first[b];first[b] = e++; 22 } 23 24 int bfs(){ 25 int rear = 0; 26 memset(d,-1,sizeof(d)); 27 d[S] = 0;q[rear++] = S; 28 for(int i = 0;i < rear;i++){ 29 for(int j = first[q[i]];j != -1;j = next[j]) 30 if(w[j] && d[v[j]] == -1){ 31 d[v[j]] = d[q[i]] + 1; 32 q[rear++] = v[j]; 33 if(v[j] == T) return 1; 34 } 35 } 36 return 0; 37 } 38 39 int dfs(int cur,int a){ 40 if(cur == T) return a; 41 for(int &i = work[cur];i != -1;i = next[i]){ 42 if(w[i] && d[v[i]] == d[cur] + 1) 43 if(int t = dfs(v[i],min(a,w[i]))){ 44 w[i] -= t;w[i^1] += t; 45 return t; 46 } 47 } 48 return 0; 49 } 50 51 int dinic(){ 52 int ans = 0; 53 while(bfs()){ 54 memcpy(work,first,sizeof(first)); 55 while(int t = dfs(S,INF)) ans += t; 56 } 57 return ans; 58 } 59 60 int main() 61 { 62 int n; 63 while(scanf("%d",&n) == 1){ 64 for(int i = 1;i <= n;i++){ 65 scanf("%d",&s[i]); 66 dp[i] = 1; 67 } 68 int ans = 1; 69 for(int i = 2;i <= n;i++) 70 for(int j = 1;j < i;j++) 71 if(s[i] > s[j] && dp[j] >= dp[i]){ 72 dp[i] = dp[j] + 1; 73 ans = max(ans,dp[i]); 74 } 75 init(); 76 S = 0,T = n*2+1; 77 for(int i = 1;i <= n;i++){ 78 add_edge(i,i+n,1); 79 if(dp[i] == 1) add_edge(S,i,1); 80 if(dp[i] == ans) add_edge(i+n,T,1); 81 for(int j = i+1;j <= n;j++){ 82 if(dp[j] == dp[i] + 1) add_edge(i+n,j,1); 83 } 84 } 85 printf("%d %d ",ans,dinic()); 86 } 87 return 0; 88 }