线性规划与网络流之6 构图、网络流

题目参见：http://www.byvoid.com/blog/lpf24-solution/

题意：给定A[1],A[2]…A[N]

Question1：最长上升子序列的长度是多少？

Question2：从这个序列中，最多能取出多少个没有重复使用的元素的上升子序列。其长度=Question1

Question3：同2，但A[1]和A[N]能使用无限次。

分析：

第一问：DP

第二问：

对于f[i]=1的点加一条边(S,i,1)

对于f[i]=len的点加一条边(i,T,1)

对于a[j]

求最大流

第三问：

在第二问的图的基础上加入以下两条边

(S,1,INF)

如果f[n]=len，加这条边(n,T,INF)

求最大流

HINT:

1、len表示第一问的答案。

2、我的程序是从0开始的。。。和分析有点出入

code:

#include #define E 4000000
#define N 1000000
using namespace std;
const int INF=0x7FFFFFFF/2;
struct gtp{int x,y,next,c,op;} g[E];
int n,a[500],f[500],e,ls[N],d[N],num[N],cur[N],fa[N],S,T,Flow;

int problem1(){
     for (int i=0;i     int ans=1;
     for (int i=1;i       for (int j=0;j         if (a[j]           f[i]=f[j]+1;
           ans=max(f[i],ans);
         }
     return ans;
}

void add(int x,int y,int c){
     e++;
     g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e; g[e].c=c; g[e].op=e+1;
     e++;
     g[e].x=y; g[e].y=x; g[e].next=ls[y]; ls[y]=e; g[e].c=0; g[e].op=e-1;
}

void relabel(int k){
     int min=T,i=ls[k];
     cur[k]=ls[k];
     while (i!=0){
       if (g[i].c>0 && d[g[i].y]       i=g[i].next;
     }
     d[k]=min+1;
}

void change(){
     int nf=INF;
     for (int i=T;i!=S;i=g[fa[i]].x)
       if (g[fa[i]].c     Flow+=nf;
     for (int i=T;i!=S;i=g[fa[i]].x){
         g[fa[i]].c-=nf;
         g[g[fa[i]].op].c+=nf;
     }
}

void sap(){
     Flow=0;
     for (int i=0;i<=T;i++){
         d[i]=0;
         num[i]=0;
         cur[i]=ls[i];
     }
     num[0]=T+1;
     int i=S;
     while (d[S]<=T){
           while (cur[i]!=0){
                 if (g[cur[i]].c>0 && d[g[cur[i]].y]+1==d[i]) break;
                 cur[i]=g[cur[i]].next;
           }
           if (cur[i]==0){
             num[d[i]]–;
             if (num[d[i]]==0) break;
             relabel(i);
             num[d[i]]++;
             if (i!=S) i=g[fa[i]].x;
           }
           else{
             fa[g[cur[i]].y]=cur[i];
             i=g[cur[i]].y;
             if (i==T){
               change();
               i=S;
             }
           }
     }
}

void problem2(int len){
     memset(ls,0,sizeof(ls));
     S=n;
     T=n+1;
     e=0;
     for (int i=0;i       if (f[i]==1) add(S,i,1);
       if (f[i]==len) add(i,T,1);
     }
     for (int i=0;i       for (int j=i+1;j         if (a[i]     sap();
     cout << Flow << endl;
}

void problem3(int len){
     memset(ls,0,sizeof(ls));
     S=n;
     T=n+1;
     e=0;
     add(S,0,INF);
     if (f[n-1]==len) add(n-1,T,INF);
     for (int i=0;i       if (f[i]==1) add(S,i,1);
       if (f[i]==len) add(i,T,1);
     }
     for (int i=0;i       for (int j=i+1;j         if (a[i]     sap();
     cout << Flow << endl;
}

int main(){
    freopen("alis.in","r",stdin);
    freopen("alis.ans","w",stdout);
    scanf("%d",&n);
    for (int i=0;i    int len=problem1();
    cout << len << endl;
    problem2(len);
    problem3(len);
    return 0;
}