BZOJ_3550_[ONTAK2010]Vacation&&BZOJ_1283:_序列

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个方程

$\begin{matrix}
xi\ge 0\\
x1+x2+x3+x4+x5\le K\\
x2+x3+x4+x5+x6\le K\\
x3+x4+x5+x6+x7\le K\\
x4+x5+x6+x7+x8\le K\\
x5+x6+x7+x8+x9\le K\\
x6+x7+x8+x9+x10\le K\\
\end{matrix}$

变成线性等式

$\begin{matrix}
xi\ge 0\\
yi\ge 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}$

差分一下增加一个方程

$\begin{matrix}
xi\ge 0\\
yi\ge 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\n",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();

}

巴特西