P2766 [网络流24题]最长不下降子序列问题

«问题描述：

给定正整数序列$x_1,...,x_n$ 。$n<=500$

求（1）计算其最长不下降子序列的长度$s$。

（2）计算从给定的序列中最多可取出多少个长度为$s$的不下降子序列。

（3）如果允许在取出的序列中多次使用$x_1$和$x_n$，则从给定序列中最多可取出多少个长度为$s$的不下降子序列。

(1)暴力n方解决

(2)建分层图，把图每个顶点i按照F[i]的不同分为若干层，这样图中从S出发到T的任何一条路径都是一个满足条件的最长不下降子序列。由 S 向所有$ f_i = 1$ 的$ i $连容量为$ 1 $的边，由所有$ f_i = s $的$ i $向$ T $连容量为$ 1$ 的边。对于所有的$ (i,j)$，若$ i < j,f_i +1 = f_j$，则由$ i$ 向$ j$ 连容量为 $1$ 的边。这样一来，所有从 $S$ 出发到达$ T$ 的的路径都是一个长度为 $s $的上升子序列。

注意拆点，以保证同一个数不会重复使用。一个连入边，一个连出边，两个点之间连流量为 1 的限制边。

注意事项: line49的条件判断注意$f[j]+1==f[i]$的前提是要$a[j]<=a[i]$才可以连边！

(3)把之前的边的流量限制改一下即可，对1号和n号微调后原样跑。

注意事项(其实网上绝大部分题解好像都忽略了)：建边时s向1号点的容量不可为无穷，应设为n, n号点连t同理.

比如这个毒瘤数据

绝大部分题解输的是INF,但其实是1

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> pii;

 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}

 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline T read(T&x){

     x=;char c;while(!isdigit(c=getchar()))if(isalpha(c))return x=(int)c;

     while(isdigit(c))x=(x<<)+(x<<)+(c^),c=getchar();return x;

 }

 const int N=+,M=+,INF=0x3f3f3f3f;

 int w[][M<<],v[][M<<],Next[][M<<],Head[][N<<],cur[][N<<],dis[][N<<],tot[],s,t,n;

 inline void Addedge(int x,int y,int z,int p){

     v[p][++tot[p]]=y,Next[p][tot[p]]=Head[p][x],Head[p][x]=tot[p],w[p][tot[p]]=z;

     v[p][++tot[p]]=x,Next[p][tot[p]]=Head[p][y],Head[p][y]=tot[p],w[p][tot[p]]=;

 }

 #define y v[p][j]

 inline char bfs(int p){

     queue<int> q;q.push(s),memset(dis[p],,sizeof dis[p]),dis[p][s]=;

     for(register int i=;i<=(n<<)+;++i)cur[p][i]=Head[p][i];

     while(!q.empty()){

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

         for(register int j=Head[p][x];j;j=Next[p][j])if(w[p][j]&&!dis[p][y]){

             dis[p][y]=dis[p][x]+,q.push(y);

             if(y==t)return ;

         }

     }

     return ;

 }

 int dinic(int x,int flow,int p){

     if(!flow||x==t)return flow;

     int rest=flow,k;

     for(register int j=cur[p][x];j&&rest;cur[p][x]=j,j=Next[p][j])if(w[p][j]&&dis[p][y]==dis[p][x]+){

         if(!(k=dinic(y,_min(rest,w[p][j]),p)))dis[p][y]=;

         rest-=k,w[p][j]-=k,w[p][j^]+=k;

     }

     return flow-rest;

 }

 #undef y

 int a[N],f[N],ans,maxflow;

 int main(){//freopen("P2766.in","r",stdin);//freopen("P2766.txt","w",stdout);

     read(n);s=(n<<)+,t=s+,tot[]=tot[]=;

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

         read(a[i]);f[i]=;

         for(register int j=;j<i;++j)if(a[j]<=a[i])MAX(f[i],f[j]+);

         for(register int j=;j<i;++j)if(f[j]+==f[i]&&a[j]<=a[i])Addedge(j+n,i,,),Addedge(j+n,i,,);

         MAX(ans,f[i]),Addedge(i,i+n,,);if(f[i]==)Addedge(s,i,,),i==?Addedge(s,i,n,):Addedge(s,i,,);

         if(i==||i==n)Addedge(i,i+n,n,);else Addedge(i,i+n,,);

     }

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

     for(register int i=;i<=n;++i)if(f[i]==ans)Addedge(i+n,t,,),i==n?Addedge(i+n,t,n,):Addedge(i+n,t,,);

     while(bfs())maxflow+=dinic(s,n,);

     printf("%d\n",maxflow);maxflow=;

     while(bfs())maxflow+=dinic(s,n,);

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

     return ;

 }

巴特西

P2766 [网络流24题]最长不下降子序列问题

最新文章

热门文章