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

3550: [ONTAK2010]Vacation

Time Limit: 10 Sec  Memory Limit: 96 MB Submit: 265  Solved: 193 [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

Sample Output

195

HINT

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

Source

By Sbullet

[Submit][Status][Discuss]

题解：单纯形

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

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

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define N 1003
#define inf 1000000000
#define eps 1e-7
using 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);
}