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);
}
}