luoguP2766 最长不下降子序列问题

原题传送门>Here<

一道网络流问题，第一问暴力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

满足条件的路径长这样：

可以发现这种建图保证了我们想要的两个性质，所以在图上跑一边网络流就是第二问的答案了。

对于第三问，我们发现限制一个点选定次数的只有它与源点、汇点的连边，以及拆出来的两个点的连边。于是我们把<S,1_x>，<1_x,1_y>,<n_x,n_y>以及<n_y,T>（如果有的话）的流改为inf就可以过第三问了。

代码：

#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);
}