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
4 4 4 6 6 6 6 6 4 4
Sample Output
30
设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();
}