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

题目传送门

这个建图啊，十分巧妙，我是真没看出来（我太蒟了）

首先要先跑一遍最长不下降子序列的\(O(n^2)\)解法，预处理出以\(i\)结尾的最长不下降子序列的长度\(dp[i]\)，然后找出最大的\(dp[i]\)，记为\(cnt\)，输出\(cnt\)，第一问就结束了。

从源点向长度为\(1\)的点连一条容量为\(1\)的边，长度为\(cnt\)的点向汇点连一条容量为\(1\)的边。因为每个点只能用一次，所以我们还要把一个点拆成两个，在它们之间连一条容量为\(1\)的边。之后\(n^2\)枚举每两个点，若两个点\(i,j\)满足\(j{<}i\)且\(dp[i]=dp[j]+1\)，则在\(i,j\)之间连一条容量为\(1\)的边。建好图后跑一边最大流，就是第二问的答案。

第三问就好办了，将源点向\(1\)连的边的容量改为\(\rm{INF}\)，\(1\)和\(1\)被拆之后的点\(1'\)之间的容量也改为\(\rm{INF}\)。同理，\(n\)和\(n'\)之间的边、\(n'\)和汇点之间的边（如果存在的话）容量也要改为\(\rm{INF}\)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF 2147483647
using namespace std;
struct zzz{
    int t,len,nex;
}e[20010<<1]; int head[10010],tot=1;
void add(int x,int y,int z){
    e[++tot].t=y;
    e[tot].len=z;
    e[tot].nex=head[x];
    head[x]=tot;
}
int dis[10010],s,t;
bool bfs(){
    memset(dis,0,sizeof(dis));
    queue <int> q; q.push(s);
    dis[s]=1;
    while(!q.empty()){
        int k=q.front(); q.pop();
        for(int i=head[k];i;i=e[i].nex){
            int to=e[i].t;
            if(dis[to]||!e[i].len) continue;
            dis[to]=dis[k]+1;
            if(to==t) return 1;
            q.push(to);
        }
    }
    return dis[t];
}
int dfs(int now,int flow){
    if(now==t||!flow) return flow;
    int rest=0,fl;
    for(int i=head[now];i;i=e[i].nex){
        int to=e[i].t;
        if(dis[to]==dis[now]+1&&(fl=dfs(to,min(e[i].len,flow)))){
            e[i].len-=fl, e[i^1].len+=fl, rest+=fl;
            if(rest==flow) return rest;
        }
    }
    if(rest<flow) dis[now]=0;
    return rest;
}
int ans;
int dinic(){
    if(bfs()) ans+=dfs(s,INF);
    return ans;
}
int read(){
    int k=0; char c=getchar();
    for(;c<'0'||c>'9';) c=getchar();
    for(;c>='0'&&c<='9';c=getchar())
      k=k*10+c-48;
    return k;
}
int a[510],dp[510],cnt;
int main(){
    int n=read(); t=(n<<1)+1;
    for(int i=1;i<=n;i++) a[i]=read(),dp[i]=1;
    for(int i=1;i<=n;i++)
      for(int j=i+1;j<=n;j++)
        if(a[j]>=a[i]) dp[j]=max(dp[j],dp[i]+1);
    for(int i=1;i<=n;i++) cnt=max(cnt,dp[i]);
    printf("%d\n",cnt);
    if(cnt==1){
        printf("%d\n%d",n,n);
        return 0;
    }
    for(int i=1;i<=n;i++){
        add(i,i+n,1); add(i+n,i,0);
        if(dp[i]==cnt) add(i+n,t,1),add(t,i+n,0);
        if(dp[i]==1) add(s,i,1),add(i,s,0);
    }
    for(int i=1;i<=n;i++)
      for(int j=1;j<i;j++){
          if(a[j]<=a[i]&&dp[j]+1==dp[i])
              add(j+n,i,1),add(i,n+j,0);
      }
    printf("%d\n",dinic());
    add(1,1+n,INF),add(n+1,1,0);
    add(n,n<<1,INF),add(n<<1,n,0);
    if(dp[1]==1) add(s,1,INF), add(1,s,0);
    if(dp[n]==cnt) add(n<<1,t,INF), add(t,n<<1,0);
    printf("%d\n",dinic());
    return 0;
}

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

原文：https://www.cnblogs.com/morslin/p/11854756.html