[codevs1906] longest increasing subsequence (dp+dinic)

Title:

I'm a hyperlink

Explanation:

It is said that it is the longest increasing subsequence, but actually it does not decrease..
Split point, split a point into two points to ensure the number of times each point is used.
After dp, it is found that when i is before J, the value of i is less than or equal to j, and the length of dp i+1=j, it can be connected from i to J.
Pay attention to the edge connecting the source point and the sink point, and the capacity of the edge that can be used as the starting point and the end point. You can control the number of uses.
The method to ensure that each point flows only once: each point has its own capacity of 1

code:

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 1e9
const int N=100005;
int a[N],b[N],tot,point[N],nxt[N*2],v[N*2],remind[N*2],cur[N],deep[N];
void clear()
{
    tot=-1;
    memset(point,-1,sizeof(point));memset(nxt,-1,sizeof(nxt));
}
void addline(int x,int y,int cap)
{
    ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; remind[tot]=cap;
    ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; remind[tot]=0;
}
bool bfs(int s,int t)
{
    queue<int>q;
    q.push(s);
    for (int i=s;i<=t;i++) cur[i]=point[i];
    memset(deep,0x7f,sizeof(deep));
    deep[s]=0;
    while (!q.empty())
    {
        int x=q.front(); q.pop();
        for (int i=point[x];i!=-1;i=nxt[i])
          if (deep[v[i]]>INF && remind[i])
            {deep[v[i]]=deep[x]+1; q.push(v[i]);}
    }
    return deep[t]<INF;
}
int dfs(int now,int t,int limit)
{
    if (now==t || !limit) return limit;
    int flow=0,f;
    for (int i=cur[now];i!=-1;i=nxt[i])
    {
        cur[now]=i;
        if (deep[v[i]]==deep[now]+1 && (f=dfs(v[i],t,min(remind[i],limit))))
        {
            flow+=f;
            limit-=f;
            remind[i]-=f;
            remind[i^1]+=f;
            if (!limit) break;
        }
    }
    return flow;
}
int dinic(int s,int t)
{
    int ans=0;
    while (bfs(s,t)) ans+=dfs(s,t,INF);
    return ans;
}
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    int maxx=0;
    for (int i=1;i<=n;i++)
    {
        int maxn=0;
        for (int j=1;j<i;j++)
          if (a[i]>=a[j] && maxn<b[j]) maxn=b[j];
        b[i]=maxn+1;
        maxx=max(maxx,b[i]);
    }
    printf("%d\n",maxx);
    //part 1
    if (maxx==1) {printf("%d\n%d",n,n);return 0;}
    clear();
    for (int i=1;i<=n;i++)
    {
        if (b[i]==1) addline(0,i,1);
        addline(i,i+n,1);
    }
    for (int i=1;i<=n;i++)
      if (b[i]==maxx) addline(i+n,2*n+1,1);
    for (int i=1;i<=n;i++)
      for (int j=i+1;j<=n;j++)
        if (a[i]<=a[j] && b[j]==b[i]+1) addline(i+n,j,1);
    printf("%d\n",dinic(0,2*n+1));
    //part 2
    clear();
    addline(0,1,INF); addline(1,1+n,INF); addline(n,2*n,INF);
    for (int i=2;i<n;i++)
    {
        if (b[i]==1) addline(0,i,1);
        addline(i,i+n,1);
    }
    for (int i=1;i<n;i++)
      if (b[i]==maxx) addline(i+n,2*n+1,1);
    if (b[n]==maxx) addline(2*n,2*n+1,INF);
    for (int i=1;i<=n;i++)
      for (int j=i+1;j<=n;j++)
        if (a[i]<=a[j] && b[j]==b[i]+1) addline(i+n,j,1);
    printf("%d\n",dinic(0,2*n+1));
    //part 3
}

Tags: less

Posted on Thu, 30 Apr 2020 11:44:18 -0700 by squariegoes