bzoj 3550: [ONTAK2010]Vacation （单纯形）

Description

有3N个数，你需要选出一些数，首先保证任意长度为N的区间中选出的数的个数<=K个，其次要保证选出的数的个数最大。

Input

第一行两个整数N，K。第二行有3N个整数。

Output

一行一个整数表示答案。

Sample Input

Sample Output

HINT

【数据范围】N<=200，K<=10。

Source

By Sbullet

题解：单纯形

这道题除了用单纯形来做还可以写网络流哦!

除了区间的个数限制以外，还要加一个限制xi<=1，然后直接上板子就可以了。

#include<iostream>#include<cstdio>#include<algorithm>#include<cstdio>#include<cmath>#define N 1003#define inf 1000000000#define eps 1e-7using namespace std;double b[N],c[N],a[N][N],ans,v;int n,k,m;void PRiov(int l,int e){	b[l]/=a[l][e];	for (int i=1;i<=n;i++)	 if (i!=e) a[l][i]/=a[l][e];	a[l][e]=1/a[l][e];	for (int i=1;i<=m;i++)	 if (fabs(a[i][e])>eps&&i!=l) {	 	b[i]-=b[l]*a[i][e];	 	for (int j=1;j<=n;j++)	 	 if (j!=e) a[i][j]-=a[i][e]*a[l][j];	 	a[i][e]=-a[i][e]*a[l][e];	 }	v+=c[e]*b[l];	for (int i=1;i<=n;i++)	 if (i!=e) c[i]-=c[e]*a[l][i];	c[e]=-c[e]*a[l][e];}double simple(){	int i,l,e;	double t;	while (true) {		for (i=1;i<=n;i++)         if (c[i]>eps) break;        e=i;        if (e==n+1) return v;        t=inf;        for (i=1;i<=m;i++)         if (a[i][e]>eps&&t>b[i]/a[i][e])          t=b[i]/a[i][e],l=i;        if (t==inf) return inf;        priov(l,e);	}}int main(){	freopen("a.in","r",stdin);	scanf("%d%d",&n,&k);	int n1=n; n*=3;	for (int i=1;i<=n;i++) scanf("%lf",&c[i]);	for (int i=1;i<=n-n1+1;i++) {		m++;		for (int j=i;j<=i+n1-1;j++)		 a[m][j]=1;		b[m]=k;	}	for (int i=1;i<=n;i++) {		m++;		a[m][i]=1; b[m]=1;	}	ans=simple();	printf("%.0lf/n",ans);}