网络流/费用流
Orz太神犇了这题……
我一开始想成跟Intervals那题一样了……每个数a[i]相当于覆盖了(a[i]-n,a[i]+n)这个区间……但是这样是错的！！随便就找出反例了……我居然还一直当正解……
实际上刚刚那个思路还有一个问题：题目中的长度为N的区间指的是给的原序列！而不是权值的区间！题就理解错了……
看了下zyf的题解，才明白过来，要用跟志愿者招募一样的方法来做；另外，志愿者招募时每种志愿者是有无限多名的，但这题中每个数只能选一次，所以边权为a[i]的边的流量不能是INF，而是1。
题解：做这题真是一种折磨。。。复习了一下根据流量平衡方程建图的方法，主要是膜拜了byvoid的志愿者招募的题解。。。让我们先列出流量平衡方程：a[i]表示i选不选，b[i]表示第i个等式的辅助变量则：0=0a[1]+a[2]+……a[n]+b[1]=ka[2]+a[3]+……a[n+1]+b[2]=k…………a[2*n+1]+a[2*n+2]+……+a[3*n]+b[2*n+1]=k0=0差分之后是a[1]+a[2]+……a[n]+b[1]=ka[n+1]-a[1]+b[2]-b[1]=0a[n+2]-a[2]+b[3]-b[2]=0…………-a[2*n+1]-a[2*n+2]-………-a[3*n]-b[2*n+1]=-k根据BYVOID所说的这段话：可以发现，每个等式左边都是几个变量和一个常数相加减，右边都为0，恰好就像网络流中除了源点和汇点的顶点都满足流量平衡。每个正的变量相当于流入该顶点的流量，负的变量相当于流出该顶点的流量，而正常数可以看作来自附加源点的流量，负的常数是流向附加汇点的流量。因此可以据此构造网络，求出从附加源到附加汇的网络最大流，即可满足所有等式。而我们还要求最小，所以要在X变量相对应的边上加上权值，然后求最小费用最大流。
所以我们构图：s=0;t=3*n+1;
for1(i,3*n)a[i]=read();
insert(s,1,k,0);insert(2*n+2,t,k,0);
for1(i,n)insert(1,i+1,1,-a[i]);
for2(i,n+1,2*n)insert(i-n+1,i+1,1,-a[i]);
for2(i,2*n+1,3*n)insert(i-n+1,2*n+2,1,-a[i]);
for1(i,2*n+1)insert(i,i+1,inf,0);需要搞清楚a[i]在哪个等式中第一次出现，在哪个等式中第二次出现，以及正负号各是什么。
b[i]的出现很显然，i为正，i+1为负
然后求最大费用最大流就可以过了。
/**************************************************************
Problem: 3550
User: Tunix
Language: C++
Result: Accepted
Time:20 ms
Memory:6016 kb
****************************************************************/ //BZOJ 3550
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
#define CC(a,b) memset(a,b,sizeof(a))
using namespace std;
int getint(){
int v=,sign=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
while(isdigit(ch)) {v=v*+ch-''; ch=getchar();}
return v*sign;
}
typedef long long LL;
const int N=,M=,INF=~0u>>;
const double eps=1e-;
/*******************template********************/
int n,m,k,a[N],b[N],c[N],w[N];
LL ans;
struct edge{int from,to,v,c;};
struct Net{
edge E[M];
int head[N],next[M],cnt;
void ins(int x,int y,int z,int c){
E[++cnt]=(edge){x,y,z,c};
next[cnt]=head[x]; head[x]=cnt;
}
void add(int x,int y,int z,int c){
ins(x,y,z,c); ins(y,x,,-c);
}
int S,T,d[N],from[N],Q[M];
bool inq[N];
bool spfa(){
int l=,r=-;
F(i,,T)d[i]=INF;
d[S]=; Q[++r]=S; inq[S]=;
while(l<=r){
int x=Q[l++]; inq[x]=;
for(int i=head[x];i;i=next[i])
if(E[i].v && d[x]+E[i].c<d[E[i].to]){
d[E[i].to]=d[x]+E[i].c;
from[E[i].to]=i;
if(!inq[E[i].to]){
Q[++r]=E[i].to;
inq[E[i].to]=;
}
}
}
return d[T]!=INF;
}
void mcf(){
int x=INF;
for(int i=from[T];i;i=from[E[i].from])
x=min(x,E[i].v);
for(int i=from[T];i;i=from[E[i].from]){
E[i].v-=x;
E[i^].v+=x;
}
ans+=x*d[T];
}
void init(){
m=n=getint(); m*=; k=getint(); cnt=;
F(i,,m) a[i]=getint();
S=; T=*n+;
add(S,,k,);
add(n*+,T,k,);
F(i,,n*+) add(i,i+,INF,); F(i,,n+) add(,i,,-a[i-]);
F(i,n+,*n+) add(i,*n+,,-a[i+n-]);
F(i,,n+) add(i,i+n,,-a[i+n-]); while(spfa()) mcf();
printf("%lld\n",-ans);
}
}G1;
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
#endif
G1.init();
return ;
}
3550: [ONTAK2010]Vacation
Time Limit: 10 Sec Memory Limit: 96 MB
Submit: 141 Solved: 105
[Submit][Status][Discuss]
Description
有3N个数，你需要选出一些数，首先保证任意长度为N的区间中选出的数的个数<=K个，其次要保证选出的数的个数最大。
Input
第一行两个整数N，K。
第二行有3N个整数。
Output
一行一个整数表示答案。
Sample Input
5 3
14 21 9 30 11 8 1 20 29 23 17 27 7 8 35
14 21 9 30 11 8 1 20 29 23 17 27 7 8 35
Sample Output
195
HINT
【数据范围】
N<=200，K<=10。