luogu P5331 [SNOI2019]通信

有匹配次数限制,求最小代价,这显然是个费用流的模型.每个点暴力和前面的点连匹配边,边数是\(n^2\)的.

然后发现可以转化成一个set,每次加入一个点,然后入点对set里面的出点连边.这个set可以用主席树实现,然后就主席树优化连边,点数边数都是\(nlogn\)的,然后就能过了

注意这里连边要把一个点入点拆成两个\(a_i,-a_i\),出点同理,然后假设\(a_i\)在set的第\(p\)位,\(a_i\)在负权值主席树上连区间\([1,p-1]\),\(-a_i\)在正权值主席树上连区间\([p+1,n]\)

然后主席树被分治连边吊打

// luogu-judger-enable-o2

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<vector>

#include<cmath>

#include<ctime>

#include<queue>

#include<map>

#include<set>

#define LL long long

#define db double

using namespace std;

const int N=1e3+10,M=3e4+10,inf=1<<29;

int rd()

{

    int x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int to[M<<2],nt[M<<2],c[M<<2],hd[M],tot=1;

LL w[M<<2];

void add(int x,int y,int z,LL zz)

{

    if(!y) return;

    ++tot,to[tot]=y,nt[tot]=hd[x],c[tot]=z,w[tot]= zz,hd[x]=tot;

    ++tot,to[tot]=x,nt[tot]=hd[y],c[tot]=0,w[tot]=-zz,hd[y]=tot;

}

LL ans,di[M];

int n,W,a[N],b[N],p[N];

bool cmp(int aa,int bb){return a[aa]<a[bb];}

int ps,pt,fw[M],pr[M];

bool v[M];

queue<int> q;

bool csfl()

{

    memset(di,0x3f,sizeof(LL)*(pt+3));

    di[ps]=0,v[ps]=1,q.push(ps);

    fw[pt]=0;

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        for(int i=hd[x];i;i=nt[i])

        {

            int y=to[i];

            if(c[i]>0&&di[y]>di[x]+w[i])

            {

                di[y]=di[x]+w[i],fw[y]=1,pr[y]=i;

                if(!v[y]) v[y]=1,q.push(y);

            }

        }

        v[x]=0;

    }

    if(!fw[pt]) return 0;

    ans+=di[pt];

    int x=pt;

    while(x!=ps)

    {

        int i=pr[x];

        c[i]-=fw[pt],c[i^1]+=fw[pt];

        x=to[i^1];

    }

    return 1;

}

int rt1,rt2,ch[M][2],t1,t2;

void inst(int o1,int o2,int x,int &tt)

{

    int l=1,r=n;

    while(l<r)

    {

        int mid=(l+r)>>1;

        if(x<=mid)

        {

            ch[o1][0]=++tt,ch[o1][1]=ch[o2][1];

            add(o1,ch[o1][0],inf,0),add(o1,ch[o1][1],inf,0);

            o1=ch[o1][0],o2=ch[o2][0];

            r=mid;

        }

        else

        {

            ch[o1][0]=ch[o2][0],ch[o1][1]=++tt;

            add(o1,ch[o1][0],inf,0),add(o1,ch[o1][1],inf,0);

            o1=ch[o1][1],o2=ch[o2][1];

            l=mid+1;

        }

    }

}

void link(int o,int l,int r,int ll,int rr,int x,int y)

{

    if(!o) return;

    if(ll<=l&&r<=rr){add(x,o,1,y);return;}

    int mid=(l+r)>>1;

    if(ll<=mid) link(ch[o][0],l,mid,ll,rr,x,y);

    if(rr>mid) link(ch[o][1],mid+1,r,ll,rr,x,y);

}

int main()

{

    n=rd(),W=rd();

    ps=0,pt=n*24+2;

    t1=n*2,t2=n*13;

    for(int i=1;i<=n;++i) a[i]=rd(),b[i]=i;

    sort(b+1,b+n+1,cmp);

    for(int i=1;i<=n;++i) p[b[i]]=i;

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

    {

        add(ps,i,1,0),add(i,pt,1,W);

        int las;

        las=rt1,rt1=++t1,inst(rt1,las,p[i],t1);

        las=rt2,rt2=++t2,inst(rt2,las,p[i],t2);

        if(p[i]>1) link(rt1,1,n,1,p[i]-1,i,a[i]);

        if(p[i]<n) link(rt2,1,n,p[i]+1,n,i,-a[i]);

        add(t1,i+n,1,-a[i]),add(t2,i+n,1,a[i]);

        add(i+n,pt,1,0);

    }

    while(csfl());

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

    return 0;

}

巴特西

luogu P5331 [SNOI2019]通信

最新文章

热门文章