luoguP2766 最长不下降子序列问题

Isonan

2018-08-14 13:48:37

Solution

原题传送门[>Here<](https://www.luogu.org/problemnew/show/P2766) 一道网络流问题,第一问暴力LIS; 对于第二问,很容易发现我们的目的是把每一个LIS表示成一条从源点到汇点的弧,同时保证每个点只用一次。可以考虑把每个点拆开,将点$i$拆成两个点$i_x,i_y$, 1.从源点向每个$f[i]=1$的$i_x$点建边,流为1; 2.从每个$i_x$向$i_y$建边,流为1; 3.对于每对$i,j(i>j)$,当num[i]>=num[j]且f[i]==f[j]+1时,从$j_y$向$i_x$建边,流为1; 4.从$f[i]=S$的$i_y$向汇点建边,流为1. 举个例子: num = 1 2 3 2 4 f = 1 2 3 3 4 ![](https://cdn.luogu.com.cn/upload/pic/28522.png) 满足条件的路径长这样: ![](https://cdn.luogu.com.cn/upload/pic/28523.png) 可以发现这种建图保证了我们想要的两个性质,所以在图上跑一边网络流就是第二问的答案了。 对于第三问,我们发现限制一个点选定次数的只有它与源点、汇点的连边,以及拆出来的两个点的连边。于是我们把$<S,1_x>$,$<1_x,1_y>$,$<n_x,n_y>$以及$<n_y,T>$(如果有的话)的流改为inf就可以过第三问了。 代码: ```cpp #include <cstdio> #include <cstring> #define min(X,Y) ((X)<(Y)?(X):(Y)) #define max(X,Y) ((X)>(Y)?(X):(Y)) int dis[2001],head[2001],nxt[600001],b[600001],v[600001],S,T,num[501],n,k=1,f[501]; int q[2001],h,t,p[2001],maxn; void push(int s,int t,int val){ nxt[++k]=head[s]; head[s]=k; b[k]=t; v[k]=val; } void link(int s,int t,int val){ push(s,t,val); push(t,s,0); } bool bfs(){ memset(dis,0,sizeof dis); dis[S]=1; h=t=0; q[++t]=S; while(h<t){ ++h; for(int i=head[q[h]];i;i=nxt[i]) if(v[i]&&!dis[b[i]]){ dis[b[i]]=dis[q[h]]+1; q[++t]=b[i]; if(b[i]==T)return 1; } } return 0; } int dfs(int x,int flow){ if(x==T||!flow)return flow; int used=0; for(int i=p[x];i;i=nxt[i]) if(v[i]&&dis[b[i]]==dis[x]+1){ int w=dfs(b[i],min(flow-used,v[i])); v[i]-=w; v[i^1]+=w; used+=w; if(w)p[x]=i; if(used==flow)return used; } if(!used)dis[x]=0; return used; } int main(){ scanf("%d",&n); S=0,T=n+n+1; for(int i=1;i<=n;i++)scanf("%d",num+i); for(int i=1;i<=n;i++){ for(int j=1;j<i;j++) if(num[j]<=num[i]&&f[j]>f[i])f[i]=f[j]; f[i]++; maxn=max(maxn,f[i]); } printf("%d\n",maxn); for(int i=1;i<=n;i++)link(i,i+n,1); for(int i=1;i<=n;i++)if(f[i]==1)link(S,i,1); for(int i=1;i<=n;i++)if(f[i]==maxn)link(i+n,T,1); for(int i=1;i<=n;i++) for(int j=1;j<i;j++) if(num[j]<=num[i]&&f[j]==f[i]-1)link(j+n,i,1); int ans=0; while(bfs()){ memcpy(p,head,sizeof p); ans+=dfs(S,0x7f7f7f7f); } printf("%d\n",ans); link(1,1+n,0x7f7f7f7f),link(S,1,0x7f7f7f7f); if(f[n]==maxn)link(n+n,T,0x7f7f7f7f),link(n,n+n,0x7f7f7f7f); while(bfs()){ memcpy(p,head,sizeof p); ans+=dfs(S,0x7f7f7f7f); } printf("%d\n",ans); } ```