로곡 P2766 최장 체증자 서열 문제

DP 최대 스트림 네트워크 스트림

제목 전송문
첫 번째 질문은 바로 DP물이 졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸졸둘째, 건도가 필요합니다.1. 각 점 i를 i.a, i.b 두 점으로 나누고 그 사이에 용량이 1인 변을 연결한다.2. 하나의 슈퍼 소스와 하나의 슈퍼 어셈블리(즉 시작점과 끝점)를 추가한다. 만약에 f[i]=1이 s와 i.a 사이에 용량이 1인 변을 연결하고 f[i]=l이 i.b와 t 사이에 용량이 1인 변을 연결한다.3. 만약에 i>j와 a[i]>a[j]와 f[j]+1=f[i]가 있다면 j.b와 i.a 사이에 용량이 1인 변을 연결한다.그리고 최대 흐름으로 뛰면 돼요!층도를 나누는 사상을 운용했고 n의 값 제목을 말하지 않았으니 틀림없이 dinic를 사용했다.세 번째는 1.a와 1.b, s 및 1.a, n.a와 n.b, n.b에서 t까지 네 변의 용량을 무한대로 늘렸으면 좋겠다.그리고 즐겁게 최대 흐름을 달렸다.
코드를 붙이려면 다음과 같이 하십시오.

#include
#include
#include
#define MAXN 5000
#define MAXM 2000005
using namespace std;
struct edge{
    int next;
    int to;
    int v;
    int flow;
};
int a[MAXN+5],f[MAXN+5];
int n,k,s;
edge ed[MAXM+5];
int h[MAXN+5],cop[MAXN+5],b[MAXN+5],dis[MAXN+5];
bool pd[MAXN+5];
void read(int x,int y,int z){
    ed[k].next=h[x]; ed[k].to=y; ed[k].v=z; ed[k].flow=0; h[x]=k; k++; 
    ed[k].next=h[y]; ed[k].to=x; ed[k].v=0; ed[k].flow=0; h[y]=k; k++;
}
bool bfs(int st,int end){
    memset(pd,false,sizeof(pd));
    int r=0,w=1;
    b[1]=st; pd[st]=true;
    dis[st]=0;
    while (rint x=b[++r];
        for (int i=h[x];i!=-1;i=ed[i].next)
            if (!pd[ed[i].to]&&ed[i].v>ed[i].flow){
                b[++w]=ed[i].to;
                pd[ed[i].to]=true;
                dis[ed[i].to]=dis[x]+1;
            }
    }
    return pd[end];
}
int dfs(int x,int y,int rem){
    if (x==y||rem==0)
        return rem;
    int sum=0;
    for (int &i=cop[x];i!=-1;i=ed[i].next)
        if (dis[ed[i].to]==dis[x]+1){
            int p=dfs(ed[i].to,y,min(ed[i].v-ed[i].flow,rem));
            if (p){
                ed[i].flow+=p; ed[i^1].flow-=p;
                sum+=p; rem-=p;
            }
        }
    return sum;
}
int maxflow(int x,int y){
    int sum=0;
    while (bfs(x,y)){
        memcpy(cop,h,sizeof(cop));
        sum+=dfs(x,y,0x7fffffff);
    }
    return sum;
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    f[1]=1;
    for (int i=1;i<=n;i++){
        for (int j=1;jif (a[i]>=a[j])
                f[i]=max(f[i],f[j]+1);
        if (!f[i]) f[i]=1;
    }
    for (int i=1;i<=n;i++)
        s=max(s,f[i]);
    printf("%d
",s);
    memset(h,-1,sizeof(h));
    int st=0,end=5003;
    for (int i=1;i<=n;i++)
        if (f[i]==1)
            read(st,i,1);
    for (int i=1;i<=n;i++)
        if (f[i]==s)
            read(i+n,end,1);
    for (int i=1;i<=n;i++)
        read(i,i+n,1);
    for (int i=1;i<=n;i++)
        for (int j=1;jif (a[i]>=a[j]&&f[j]+1==f[i])
                read(j+n,i,1);
    int ans=maxflow(st,end);
    printf("%d
",ans);
    read(1,1+n,0x7fffffff);
    read(st,1,0x7fffffff);
    if (f[n]==s){
        read(n,n+n,0x7fffffff);
        read(n+n,end,0x7fffffff);
    }
    ans+=maxflow(st,end);
    printf("%d
",ans);
    return 0;
}