BZOJ 3550 ONTAK2010 Vacation 单纯形

题目大意：给定一个长度为3n的区间。要求选一些数，且随意一段长度为n的区间内最多选k个数。求选择数的和的最大值

单纯形直接搞

注意一个数仅仅能被选一次 因此要加上xi<=1这个约束条件

不明确3n还有k<=10是为何。。

。

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define EPS 1e-7

#define INF 1e10

using namespace std;

int n,m,k;

namespace Linear_Programming{

	double A[1210][610],b[1210],c[610],v;

	void Pivot(int l,int e)

	{

		int i,j;

		b[l]/=A[l][e];

		for(i=1;i<=n;i++)

			if(i!=e)

				A[l][i]/=A[l][e];

		A[l][e]=1/A[l][e];

		for(i=1;i<=m;i++)

			if(i!=l&&fabs(A[i][e])>EPS)

			{

				b[i]-=A[i][e]*b[l];

				for(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(i=1;i<=n;i++)

			if(i!=e)

				c[i]-=c[e]*A[l][i];

		c[e]=-c[e]*A[l][e];

	}

	double Simplex()

	{

		int i,l,e;

		while(1)

		{

			for(i=1;i<=n;i++)

				if(c[i]>EPS)

					break;

			if((e=i)==n+1)

				return v;

			double temp=INF;

			for(i=1;i<=m;i++)

				if( A[i][e]>EPS && b[i]/A[i][e]<temp )

					temp=b[i]/A[i][e],l=i;

			if(temp==INF) return INF;

			Pivot(l,e);

		}

	}

}

int main()

{

	using namespace Linear_Programming;

	int i,j;

	cin>>n>>k;

	for(i=1;i<=n*3;i++)

		scanf("%lf",&c[i]);

	for(i=1;i+n-1<=n*3;i++)

	{

		b[++m]=k;

		for(j=i;j<=i+n-1;j++)

			A[m][j]=1;

	}

	for(i=1;i<=n*3;i++)

	{

		b[++m]=1;

		A[m][i]=1;

	}

	n*=3;

	double ans=Simplex();

	cout<<int(ans+0.5)<<endl;

	return 0;

}