程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BZOJ 3112 Zjoi2013 防守戰線 單純形

BZOJ 3112 Zjoi2013 防守戰線 單純形

編輯:C++入門知識

BZOJ 3112 Zjoi2013 防守戰線 單純形


題目大意:

\

單純形*2。。。

 

#include 
#include 
#include 
#include 
#include 
#define EPS 1e-7
#define INF 1e10
using namespace std;
int n,m;
namespace Linear_Programming{
	double A[1010][10100],b[1010],c[10100],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]>m>>n;
	for(i=1;i<=m;i++)www.Bkjia.com
		scanf("%lf",&b[i]);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		for(j=x;j<=y;j++)
			A[j][i]=1;
		c[i]=z;
	}
	double ans=Simplex();
	cout<<(long long)(ans+0.5)<

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved