【Luogu】P2766最长不下降子序列问题（暴力网络流）

　　题目链接

　　水题qwq，数据都那么水。

　　我要是出数据的人我就卡$n^3$建图。

　　qwq。

　　然而这么水的题我！居！然！没！有！1！A！！还！提！交！了！五！遍！！！

　　md从现在开始要锻炼1A率了

　　看我从今往后做完一道题之后至少检查TM十分钟

　　可恶qwq。

　　第一问$n^2$sbDP可解。然而你们知道我提交五遍TM是错在哪里了吗？？？？？

　　我TM就错在这个pj-，sb到不能再sb的sb暴力DP上！！！

　　气死我了！！！

　　关于第二问和第三问，先拆点再拆点qwq。

　　先把每个点拆成入点和出点用来限制流量，然后把出点拆成s个点为的是跑最大流的时候统计比较方便。

　　能跑到汇点就是一种方式，跑不到就说明没有那么长的最长不下降子序列。

　　第三问暴力修改边容量再跑一遍即可。

　　qwqqqqqqqqq我网络流都没写错栽在一个入门DP上

　　qwqqqqqq

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<queue>

#define maxm 200010

using namespace std;

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

int n,m;

int q[];

int s[];

int ne[][],tot[];

int Start,End;

inline int count(int i){    return i&?i+:i-;    }

struct Edge{

    int next,to,val;

}edge[maxm*];

int head[maxm],num;

inline void addedge(int from,int to,int val){

    edge[++num]=(Edge){head[from],to,val};

    head[from]=num;

}

inline void add(int from,int to,int val){

    addedge(from,to,val);

    addedge(to,from,);

}

bool vis[maxm];

int dfn[maxm];

int list[maxm];

bool bfs(){

    memset(vis,,sizeof(vis));    vis[Start]=;    dfn[Start]=;

    queue<int>q;    q.push(Start);

    while(!q.empty()){

        int from=q.front();q.pop();

        for(int i=head[from];i;i=edge[i].next){

            int to=edge[i].to;

            if(edge[i].val==||vis[to])    continue;

            vis[to]=;    dfn[to]=dfn[from]+;

            q.push(to);

        }

    }

    return vis[End];

}

int dfs(int x,int val){

    if(x==End||val==)    return val;

    int flow=;    vis[x]=;

    for(int &i=list[x];i;i=edge[i].next){

        int to=edge[i].to;

        if(vis[to]||edge[i].val==||dfn[to]!=dfn[x]+)    continue;

        int now=dfs(to,min(val,edge[i].val));

        val-=now;    flow+=now;    edge[i].val-=now;    edge[count(i)].val+=now;

        if(val<=)    break;

    }

    if(val!=flow)    dfn[x]=-;

    return flow;

}

int maxflow(){

    int ans=;

    while(bfs()){

        memset(vis,,sizeof(vis));

        for(int i=Start;i<=End;++i)    list[i]=head[i];

        int now=dfs(Start,0x7fffffff);

        if(!now)    break;

        ans+=now;

    }

    return ans;

}

int main(){

    int n=read();

    for(int i=;i<=n;++i){

        q[i]=read();s[i]=;

    }

    m=;

    for(int i=n-;i>=;--i){

        for(int j=i+;j<=n;++j){

            if(q[i]>q[j])    continue;

            if(s[i]<s[j]+)    s[i]=s[j]+;

            if(m<s[i])    m=s[i];

        }

    }

    printf("%d\n",m);

    End=(m+)*n+n+;

    for(int i=;i<=n;++i){

        add(Start,i,0x7fffffff);

        add(i,i+n,);

        add(m*n+i,End,);

        for(int j=i+;j<=n;++j){

            if(q[i]>q[j])    continue;

            for(register int k=;k<m;++k)    add(k*n+i,(k+)*n+j,);

        }

    }

    int ans=maxflow();

    printf("%d\n",ans);

    int ret=;

    for(int j=head[ret];j;j=edge[j].next){

        int to=edge[j].to;

        if(to<ret)    continue;

        edge[j].val+=;

    }

    /*for(int j=head[1];j;j=edge[j].next){

        int to=edge[j].to;

        edge[j].val+=1234567;

    }*/

    ret=m*n+n;

    for(int j=head[ret];j;j=edge[j].next){

        int to=edge[j].to;

        if(to!=End)    continue;

        edge[j].val+=;

    }

    printf("%d",ans+maxflow());

    return ;

}

巴特西

【Luogu】P2766最长不下降子序列问题（暴力网络流）

最新文章

热门文章