BZOJ_3550_[ONTAK2010]Vacation&&BZOJ_1283:_序列_网络流解线性规划

Description

给出一个长度为的正整数序列Ci，求一个子序列，使得原序列中任意长度为的子串中被选出的元素不超过K(K,M<=100) 个，并且选出的元素之和最大。

Input

第1行三个数N,m,k。接下来N行，每行一个字符串表示Ci。

Output

最大和。

Sample Input

10 5 3
4 4 4 6 6 6 6 6 4 4

Sample Output

设xi为第i个数是否选。

于是我们有n-m+1个方程

$egin{matrix}
xige 0\
x1+x2+x3+x4+x5le K\
x2+x3+x4+x5+x6le K\
x3+x4+x5+x6+x7le K\
x4+x5+x6+x7+x8le K\
x5+x6+x7+x8+x9le K\
x6+x7+x8+x9+x10le K\
end{matrix}$

变成线性等式

$egin{matrix}
xige 0\
yige 0\
x1+x2+x3+x4+x5+y1=K\
x2+x3+x4+x5+x6+y2=K\
x3+x4+x5+x6+x7+y3=K\
x4+x5+x6+x7+x8+y4=K\
x5+x6+x7+x8+x9+y5=K\
x6+x7+x8+x9+x10+y6=K\
end{matrix}$

差分一下增加一个方程

$egin{matrix}
xige 0\
yige 0\
x1+x2+x3+x4+x5+y1-K=0\
x6-x1+y2-y1=0\
x7-x2+y3-y2=0\
x8-x3+y4-y3=0\
x9-x4+y5-y4=0\
x10-x5+y6-y5=0\
-x6-x7-x8-x9-x10-y6+K=0\
end{matrix}$

然后建图跑最大费用最大流。

对于方程，建立n-m+1个点，对于变量x,找到系数为+1的方程位置和系数为-1的方程位置连边(inf,a[i])。

对于y变量连i->i+1(inf,0)。S->1(K,0),n-m+2->T(K,0)。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1050
#define M 100050
#define S (n-m+3)
#define T (n-m+4)
#define inf (1<<30)
int head[N],to[M],nxt[M],cnt=1,path[N],dis[N],Q[N],l,r,inq[N],flow[M],val[M];
int n,m,K,a[N];
inline void add(int u,int v,int f,int w) {
    to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; flow[cnt]=f; val[cnt]=w;
    to[++cnt]=u; nxt[cnt]=head[v]; head[v]=cnt; flow[cnt]=0; val[cnt]=-w;
}
bool spfa() {
    memset(dis,0x80,sizeof(dis));
    memset(path,0,sizeof(path));
    l=r=0; Q[r++]=S; dis[S]=0; inq[S]=1;
    while(l!=r) {
        int x=Q[l++],i; if(l==T+1) l=0; inq[x]=0;
        for(i=head[x];i;i=nxt[i]) {
            if(flow[i]&&dis[to[i]]<dis[x]+val[i]) {
                dis[to[i]]=dis[x]+val[i];
                path[to[i]]=i^1; 
                if(!inq[to[i]]) {
                    inq[to[i]]=1; Q[r++]=to[i]; if(r==T+1) r=0;
                }
            }
        }
    }
    return path[T];
}
void mcmf() {
    int minc=0,maxf=0,i;
    while(spfa()) {
        int nf=1<<30;
        for(i=T;i!=S;i=to[path[i]]) {
            nf=min(nf,flow[path[i]^1]);
        }
        for(i=T;i!=S;i=to[path[i]]) {
            flow[path[i]]+=nf; 
            flow[path[i]^1]-=nf;
            minc+=nf*val[path[i]^1];
        }
        maxf+=nf;
    }
    printf("%d
",minc);
}
int main() {
    scanf("%d%d%d",&n,&m,&K);
    int i;
    for(i=1;i<=n;i++) {
        scanf("%d",&a[i]);
    }
    add(S,1,K,0); add(n-m+2,T,K,0);
    for(i=1;i<=n-m+1;i++) add(i,i+1,inf,0);
    for(i=1;i<=n;i++) {
        if(i<=m) add(1,i+1,1,a[i]);
        else if(i>n-m) add(i-m+1,n-m+2,1,a[i]);
        else add(i-m+1,i+1,1,a[i]);
    }
    mcmf();
}