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

洛谷传送门 LOJ传送门

第一问暴力$O(n^2)$转移就行了

第二问有坑，题目的意思是从序列里取出来一些数，取出来的数不放回去，才有了第三问

图还是比较好建的吧，源点向$f[i]=1$的点连流量为$1$的边，点$i$向$f[j]=f[i]+1$的$j$点连流量为$1$的边，$f[i]=s$的$i$点向汇点连流量为$1$的边

这样建图，保证了每一条流向汇点的流量都是跑了$s$条边的。

然后跑最大流就行了

第三问细节比较多，题目也有坑

首先题目的意思是$x1,xn$可以出现在多组最长不下降子序列中，但在一组里只能出现一次！

源点向$1$连流量为$inf$的边，$n$向汇点连流量为$inf$的边

然而可能会出现$f[n]!=s$的情况，会导致$1$的流量经过少于$s$条边到达$n$点

还会出现$s=1$的情况，不能特判掉等等

提供一组数据吧

23
749 917 271 938 366 953 64 723 678 448 754 112 831 228 684 601 506 121 6 417 382 724 1

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #define N1 505
  5 #define M1 50010
  6 #define ll long long
  7 #define dd double
  8 #define inf 0x3f3f3f3f
  9 using namespace std;
 10 
 11 int gint()
 12 {
 13     int ret=0,fh=1;char c=getchar();
 14     while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}
 15     while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
 16     return ret*fh;
 17 }
 18 int n,m,nn,S,T,len;
 19 int a[N1];
 20 struct Edge{
 21 int head[N1],to[M1<<1],nxt[M1<<1],flow[M1<<1],cte;
 22 void ae(int u,int v,int F)
 23 {
 24     cte++; to[cte]=v; flow[cte]=F;  
 25     nxt[cte]=head[u]; head[u]=cte;
 26 }
 27 }e,E;
 28 
 29 int que[N1],hd,tl,dep[N1],cur[N1];
 30 int bfs()
 31 {
 32     int x,j,v;
 33     memset(dep,-1,sizeof(dep)); memcpy(cur,E.head,sizeof(cur));
 34     hd=1,tl=0; que[++tl]=S; dep[S]=0; 
 35     while(hd<=tl)
 36     {
 37         x=que[hd++];
 38         for(j=E.head[x];j;j=E.nxt[j])
 39         {
 40             v=E.to[j];
 41             if( dep[v]==-1 && E.flow[j]>0 )
 42                 dep[v]=dep[x]+1, que[++tl]=v; 
 43         }
 44     }
 45     return dep[T]!=-1;
 46 }
 47 int dfs(int x,int limit)
 48 {
 49     int j,v,flow,ans=0; if(x==T||!limit) return limit;
 50     for(j=cur[x];j;j=E.nxt[j])
 51     {
 52         cur[x]=j; v=E.to[j];
 53         if( dep[v]==dep[x]+1 && (flow=dfs(v,min(E.flow[j],limit))) )
 54         {
 55             limit-=flow; ans+=flow;
 56             E.flow[j]-=flow; E.flow[j^1]+=flow;
 57             if(!limit) break;
 58         }
 59     }
 60     return ans;
 61 }
 62 int f[N1],vis[N1];
 63 int Dinic1()
 64 {
 65     int mxflow=0;
 66     memcpy(&E,&e,sizeof(E));
 67     while(bfs()) mxflow+=dfs(S,inf);
 68     return mxflow;
 69 }
 70 int Dinic2()
 71 {
 72     int mxflow=0,i;
 73     memcpy(&E,&e,sizeof(E));
 74     E.ae(S,1,inf),E.ae(1,S,0);
 75     E.ae(n,T,inf),E.ae(T,n,0);
 76     while(bfs()) mxflow+=dfs(S,inf);
 77     if(len!=1&&(f[n]!=len||f[1]+1>f[n])) mxflow--;
 78     return mxflow;
 79 }
 80 
 81 int main()
 82 {
 83     scanf("%d",&n);
 84     int i,j; S=n+1,T=n+2; e.cte=1;
 85     for(i=1;i<=n;i++) a[i]=gint();
 86     for(i=1;i<=n;i++)
 87         for(j=1,f[i]=1;j<i;j++) if(a[j]<=a[i])
 88             f[i]=max(f[i],f[j]+1);
 89     for(i=1;i<=n;i++) len=max(len,f[i]);
 90     printf("%d
",len);
 91     for(i=1;i<=n;i++)   
 92     {
 93         if(f[i]==len) e.ae(i,T,1), e.ae(T,i,0);
 94         if(f[i]==1) e.ae(S,i,1), e.ae(i,S,0);
 95         else{
 96             for(j=1;j<i;j++) 
 97             if(f[i]==f[j]+1&&a[j]<=a[i]) 
 98                 e.ae(j,i,1), e.ae(i,j,0);
 99         }
100     }
101     printf("%d
",Dinic1());
102     printf("%d
",Dinic2());
103     return 0;
104 }