loj6005 [网络流24题]最长递增子序列

题意：给你一个序列，求不严格上升lcs长度/最多有几个没有重复元素的lcs/如果x1和xn可以多次出现，求最多有几个lcs？n<=500.

标程：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int N=;

 const int inf=0x3f3f3f3f;

 queue<int> q;

 int cnt=,dis[N],S,T,x1,xn,a[N],f[N],Head[N],ans,head[N],n,Max,tmp,ans1;

 struct node{int to,next,w;}num[N*N*];

 void add(int x,int y,int w)

 {num[++cnt].to=y;num[cnt].next=head[x];num[cnt].w=w;head[x]=cnt;

 num[++cnt].to=x;num[cnt].next=head[y];num[cnt].w=;head[y]=cnt;}

 void build()

 {

     for (int i=;i<=n;i++)

       for (int j=i+;j<=n;j++)

         if (a[i]<=a[j]&&f[i]+==f[j]) add((i==)?x1:((i==n)?xn:i),j,);

     for (int i=;i<=n;i++)

     {

         if (f[i]==) add(S,i,);

        if (f[i]==Max) add((i==)?x1:((i==n)?xn:i),T,);

     }

     add(,x1,);add(n,xn,);

 }

 bool bfs()

 {

     memset(dis,,sizeof(dis));dis[S]=;

     q.push(S);

     while (!q.empty())

     {

         int now=q.front();q.pop();

         for (int i=head[now];i;i=num[i].next)

           if (num[i].w&&!dis[num[i].to])

             dis[num[i].to]=dis[now]+,q.push(num[i].to);

     }

     return dis[T]!=;

 }

 int dfs(int x,int mm)

 {

     int tmp=mm;

     if (x==T) return mm;

     for (int &i=Head[x];i&&tmp;i=num[i].next)

       if (num[i].w&&dis[num[i].to]==dis[x]+)

       {

             int t=dfs(num[i].to,min(num[i].w,tmp));

             tmp-=t;num[i].w-=t;num[i^].w+=t;

       }

     return mm-tmp;

 }

 void dinic()

 {

     while (bfs())

     {

         memcpy(Head,head,sizeof(head));

         while (tmp=dfs(S,inf)) ans+=tmp;

     }

 }

 int main()

 {

     scanf("%d",&n);S=n+;T=S+;x1=T+;xn=x1+;

     for (int i=;i<=n;i++) scanf("%d",&a[i]);

     f[]=;

     for (int i=;i<=n;i++)

     {

         for (int j=;j<i;j++)

         if (a[i]>=a[j]) f[i]=max(f[i],f[j]);

        f[i]++;

     }

     for (int i=;i<=n;i++) Max=max(Max,f[i]);

     printf("%d\n",Max);

     build();dinic();

     printf("%d\n",ans);ans1=ans;

     add(,x1,inf);add(n,xn,inf);

     for (int i=;i<=n;i++)

     {

         if (f[i]==) add(S,i,inf);

        if (f[i]==Max) add((i==)?x1:((i==n)?xn:i),T,inf);

     }

     dinic();

     if (Max==) printf("%d\n",ans1);else printf("%d\n",ans);

    return ;

 }

易错点：1.需要特判lcs=1时询问3的答案和询问2是一样的。不然会错。

题解：网络流+拆点

第一问直接dp。

第二问对于i<j&&a[i]<=a[j]&&f[i]+1==f[j]的(i,j)连容量为1的边，f[i]=1向S连边，f[i]=Max向T连边。跑最大流。

第三问可以直接在第二问的残图上跑，对于x1和xn点拆点（可以在第二问建图时就拆好），设置点流量为inf。同时对于所有向源汇连的边都设为inf。