hdu6611

求k个不相交子序列，让其和最大。使用dij费用流即可
做法一: 用主席树优化建图，用dp优化第一次dij算法

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
struct MCMF{
    static const int maxn=2005*20*2,maxm=2+3*2005+2005*20*4;
    struct star{int v,nex,c,w;} edge[maxm<<1];

    int head[maxn],cnt,n;
    int pre[maxn],dist[maxn],h[maxn];// h -> 势能函数

    void ini(int point){
        cnt=-1;n=point;
        for(int i=0;i<=n;i++) head[i]=-1,h[i]=0;
    }
    void add_edge(int u, int v, int c, int w){
//        cout<<"     "<<u<<" "<<v<<" "<<c<<" "<<w<<endl;
        edge[++cnt]=star{v,head[u],c, w}; head[u]=cnt;
        edge[++cnt]=star{u,head[v],0,-w}; head[v]=cnt;
    }
    void minCostMaxFlow(int s, int t,int&flow,int&cost){//dij
        flow=cost=0;
        while(true){
            for(int i=0;i<=n;i++) dist[i]=2e9;
            dist[s]=0;
            priority_queue<pii,vector<pii>,greater<pii>>que; que.push(pii(dist[s],s));
            while(!que.empty()){
                int u=que.top().second,dis=que.top().first; que.pop();
                if (dist[u]!=dis) continue;
                for(int i=head[u];~i;i=edge[i].nex){
                    int v=edge[i].v,c=edge[i].c,w=edge[i].w;
                    if(c>0&&dist[v]>dist[u]+w+h[u]-h[v]){
                        dist[v]=dist[u]+w+h[u]-h[v];
//                        assert(dist[v]>=0);
                        pre[v]=i;
                        que.push(pii(dist[v],v));
                    }
                }
            }
            if(dist[t]==2e9) break;
            for(int i=0;i<=n;i++) h[i]+=dist[i];// d[i]=dist[i]+h[i]-h[s]=dist[i]+h[i]
            int addf=2e9;
            for(int x=t;x!=s;x=edge[pre[x]^1].v) addf=min(addf,edge[pre[x]].c);
            for(int x=t;x!=s;x=edge[pre[x]^1].v) {
                edge[pre[x]].c-=addf;
                edge[pre[x]^1].c+=addf;
            }
            flow+=addf;
            cost+=h[t]*addf;
        }
    }
}g;

int a[2005],n,k,s,t;

//主席树优化建图 dp优化dij
#define ml ((l+r)>>1)
#define mr (ml+1)
const int maxn = 2005;
int ls[maxn*20],rs[maxn*20],tot,rt[maxn];//update用了几次，就要乘以多少

void update(int pre,int&u,int l,int r,int pos,int dst){//把u按照pre复制，然后更新pos
    u=++tot;
    ls[u]=ls[pre];rs[u]=rs[pre];
    if(pre!=0) {
        g.add_edge((pre+n+2)<<1|1,(u+n+2)<<1,k,0); // k flow
        g.h[(u+n+2)<<1]=g.h[(u+n+2)<<1|1]=min(g.h[(pre+n+2)<<1],g.h[dst<<1|1]);
    }
    else g.h[(u+n+2)<<1]=g.h[(u+n+2)<<1|1]=g.h[dst<<1|1];
    g.add_edge(dst<<1|1,(u+n+2)<<1,k,0);// k flow
    g.add_edge((u+n+2)<<1,(u+n+2)<<1|1,k,0);// k flow
    if(l==r)return;
    if(pos<=ml) update(ls[pre],ls[u],l,ml,pos,dst);
    else update(rs[pre],rs[u],mr,r,pos,dst);
}

void query(int u,int l,int r,int pos,int dst){
    if(r<=pos){
        if(u!=0) {
            g.add_edge((u+n+2)<<1|1,dst<<1,k,0);// k flow
            g.h[dst<<1]=min(g.h[dst<<1],g.h[(u+n+2)<<1]);
        }
        g.h[dst<<1|1]=g.h[dst<<1]-pos;
        return;
    }
    if(l>pos) return;
    query(ls[u],l,ml,pos,dst);
    query(rs[u],mr,r,pos,dst);
}

void build_graph(){
    tot=0;
    g.ini(n*20*2);

    s=n+1,t=n+2;
    g.add_edge(s<<1,s<<1|1,k,0);// k flow
    g.h[s<<1]=g.h[s<<1|1]=0;

    int mim=0;
    for(int i=1;i<=n;i++) mim=max(mim,a[i]);

    for(int i=1;i<=n;i++) {
        g.add_edge(s<<1|1,i<<1,k,0);// k flow
        g.add_edge(i<<1,i<<1|1,1,-a[i]);// 1 flow
        g.add_edge(i<<1|1,t<<1,k,0);// k flow

        query(rt[i-1],1,mim,a[i],i);
        update(rt[i-1],rt[i],1,mim,a[i],i);
    }
    g.add_edge(t<<1,t<<1|1,k,0);// k flow
    g.h[t<<1]=g.h[t<<1|1]=g.h[(rt[n]+n+2)<<1];
}
///////////////////////////
//究极读入挂
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    char ch=nc();int sum=0;
    while(!(ch>='0'&&ch<='9'))ch=nc();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    return sum;
}


int main(){
//    freopen("/Users/s/Downloads/2019HDOJ多校3_UESTC/data/1009/multi.in","r",stdin);
    int ti=read();
    while(ti--){
        n=read();k=read();
        for(int i=1;i<=n;i++) a[i]=read();

        build_graph();

        int flow,cost;
        g.minCostMaxFlow(s<<1,t<<1|1,flow,cost);
        printf("%d\n",-cost);
        //cout<<-cost<<endl;
    }
}

做法二：用主席树优化建图，用spfa优化第一次dij算法

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
struct MCMF{
    static const int maxn=2005*20*2,maxm=2+3*2005+2005*20*4;
    struct star{int v,nex,c,w;} edge[maxm<<1];

    int head[maxn],cnt,n;
    int pre[maxn],dist[maxn],h[maxn];// h -> 势能函数

    void ini(int point){
        cnt=-1;n=point;
        for(int i=0;i<=n;++i) head[i]=-1,h[i]=0;
    }
    void add_edge(int u, int v, int c, int w){
//        cout<<"     "<<u<<" "<<v<<" "<<c<<" "<<w<<endl;
        edge[++cnt]=star{v,head[u],c, w}; head[u]=cnt;
        edge[++cnt]=star{u,head[v],0,-w}; head[v]=cnt;
    }
    void minCostMaxFlow_dij(int s, int t,int&flow,int&cost){//dij
        flow=cost=0;
        while(true){
            for(int i=0;i<=n;++i) dist[i]=2e9;
            dist[s]=0;
            priority_queue<pii,vector<pii>,greater<pii>>que; que.push(pii(dist[s],s));
            while(!que.empty()){
                int u=que.top().second,dis=que.top().first; que.pop();
                if (dist[u]!=dis) continue;
                for(int i=head[u];~i;i=edge[i].nex){
                    int v=edge[i].v,c=edge[i].c,w=edge[i].w;
                    if(c>0&&dist[v]>dist[u]+w+h[u]-h[v]){
                        dist[v]=dist[u]+w+h[u]-h[v];
//                        assert(dist[v]>=0);
                        pre[v]=i;
                        que.push(pii(dist[v],v));
                    }
                }
            }
            if(dist[t]==2e9) break;
            for(int i=0;i<=n;++i) h[i]+=dist[i];// d[i]=dist[i]+h[i]-h[s]=dist[i]+h[i]
            int addf=2e9;
            for(int x=t;x!=s;x=edge[pre[x]^1].v) addf=min(addf,edge[pre[x]].c);
            for(int x=t;x!=s;x=edge[pre[x]^1].v) {
                edge[pre[x]].c-=addf;
                edge[pre[x]^1].c+=addf;
            }
            flow+=addf;
            cost+=h[t]*addf;
        }
    }
    void minCostMaxFlow(int s, int t,int&flow,int&cost){//spfa 用来先负权图处理
        for(int i=0;i<=n;++i) dist[i]=2e9;
        dist[s]=0;
        queue<pii>que; que.push(pii(dist[s],s));
        while(!que.empty()){
            int u=que.front().second,dis=que.front().first; que.pop();
            if (dist[u]!=dis) continue;
            for(int i=head[u];~i;i=edge[i].nex){
                int v=edge[i].v,c=edge[i].c,w=edge[i].w;
                if(c>0&&dist[v]>dist[u]+w){
                    dist[v]=dist[u]+w;
                    pre[v]=i;
                    que.push(pii(dist[v],v));
                }
            }
        }
        if(dist[t]==2e9) return;
        for(int i=0;i<=n;++i) h[i]=dist[i];// d[i]=dist[i]+h[i]-h[s]=dist[i]+h[i]
        int addf=2e9;
        for(int x=t;x!=s;x=edge[pre[x]^1].v) addf=min(addf,edge[pre[x]].c);
        for(int x=t;x!=s;x=edge[pre[x]^1].v) {
            edge[pre[x]].c-=addf;
            edge[pre[x]^1].c+=addf;
        }
        int oldh=h[t];
        minCostMaxFlow_dij(s,t,flow,cost);
        flow+=addf;
        cost+=oldh*addf;
    }
}g;

int a[2005],n,k,s,t;

//主席树优化建图 dp优化dij
#define ml ((l+r)>>1)
#define mr (ml+1)
const int maxn = 2005;
int ls[maxn*20],rs[maxn*20],tot,rt[maxn];//update用了几次，就要乘以多少

void update(int pre,int&u,int l,int r,int pos,int dst){//把u按照pre复制，然后更新pos
    u=++tot;
    ls[u]=ls[pre];rs[u]=rs[pre];
    if(pre!=0) g.add_edge((pre+n+2)<<1|1,(u+n+2)<<1,k,0); // k flow
    g.add_edge(dst<<1|1,(u+n+2)<<1,k,0);// k flow
    g.add_edge((u+n+2)<<1,(u+n+2)<<1|1,k,0);// k flow
    if(l==r)return;
    if(pos<=ml) update(ls[pre],ls[u],l,ml,pos,dst);
    else update(rs[pre],rs[u],mr,r,pos,dst);
}

void query(int u,int l,int r,int pos,int dst){
    if(r<=pos){
        if(u!=0)g.add_edge((u+n+2)<<1|1,dst<<1,k,0);// k flow
        return;
    }
    if(l>pos) return;
    query(ls[u],l,ml,pos,dst);
    query(rs[u],mr,r,pos,dst);
}

void build_graph(){
    tot=0;
    g.ini(n*20*2);

    s=n+1,t=n+2;
    g.add_edge(s<<1,s<<1|1,k,0);// k flow

    int mim=0;
    for(int i=1;i<=n;++i) mim=max(mim,a[i]);

    for(int i=1;i<=n;++i) {
        g.add_edge(s<<1|1,i<<1,k,0);// k flow
        g.add_edge(i<<1,i<<1|1,1,-a[i]);// 1 flow
        g.add_edge(i<<1|1,t<<1,k,0);// k flow

        query(rt[i-1],1,mim,a[i],i);
        update(rt[i-1],rt[i],1,mim,a[i],i);
    }
    g.add_edge(t<<1,t<<1|1,k,0);// k flow
}

///////////////////////////
//究极读入挂
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    char ch=nc();int sum=0;
    while(!(ch>='0'&&ch<='9'))ch=nc();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    return sum;
}


int main(){
//    freopen("/Users/s/Downloads/2019HDOJ多校3_UESTC/data/1009/multi.in","r",stdin);
    int ti=read();
    while(ti--){
        n=read();k=read();
        for(int i=1;i<=n;++i) a[i]=read();

        build_graph();

        int flow,cost;
        g.minCostMaxFlow(s<<1,t<<1|1,flow,cost);
        printf("%d\n",-cost);
    }
}