记录编号	115109	评测结果	AAAAAAAAAA
题目名称	[UVa 10498] 满意值	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2014-08-14 11:08:12	内存使用	0.65 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int SIZEN=210;
const double eps=1e-10,INF=1e10;
class Liner_Programming{
public:
	//基变量=因变量,非基变量=自变量
	int N;//总数,从1~N
	double A[SIZEN][SIZEN];//A[i]的表达式包含-A[i][j]*x[j]这一项
	double c[SIZEN];//目标函数是sigma{c[i]*x[i]}
	double b[SIZEN];//A[i]的常数
	bool bas[SIZEN];//是否是因变量(基本变量)
	double v;
	void print(void){
		cout<<"v = "<<v<<endl;
		cout<<"目标 = ";for(int i=1;i<=N;i++) if(!bas[i]) cout<<c[i]<<"x"<<i<<" + ";cout<<endl;
		for(int i=1;i<=N;i++){
			if(bas[i]){
				cout<<"x"<<i<<" = "<<b[i]<<" - ";
				for(int j=1;j<=N;j++){
					if(!bas[j]) cout<<A[i][j]<<"x"<<j<<" - ";
				}
				cout<<endl;
			}
		}
	}
	void clear(void){
		N=0;
		memset(A,0,sizeof(A));
		memset(c,0,sizeof(c));
		memset(b,0,sizeof(b));
		memset(bas,0,sizeof(bas));
		v=0;
	}
	Liner_Programming(){clear();}
	void Pivot(int l,int e){//将基变量l和非基变量e进行调换
		//将e改成基变量,l改成非基变量
		//原先:x[l]=b[l]-sigma{A[l][j]*x[j]}
		bas[e]=true,bas[l]=false;
		v+=c[e]*(b[l]/A[l][e]);//至多增加这么多
		//x[e]*A[l][e]=b[l]-sigma{A[l][j]*x[j]}-x[l]
		//x[e]=b[l]/A[l][e]-sigma{A[l][j]/A[l][e]*x[j]}-x[l]/A[l][e]
		//下面更新c
		for(int i=1;i<=N;i++){
			if(!bas[i]&&i!=e){
				c[i]-=A[l][i]/A[l][e]*c[e];
			}
		}
		c[l]=-1.0/A[l][e]*c[e];
		//下面更新b
		for(int i=1;i<=N;i++){
			if(bas[i]&&i!=l){
				b[i]-=b[l]/A[l][e]*A[i][e];
			}
		}
		b[e]=b[l]/A[l][e];
		//下面更新A
		for(int i=1;i<=N;i++){
			if(bas[i]&&i!=l){
				for(int j=1;j<=N;j++){
					if(!bas[j]&&j!=e){
						A[i][j]-=A[i][e]*A[l][j]/A[l][e];
					}
				}
				A[i][l]=-A[i][e]/A[l][e];
			}
		}
		for(int i=1;i<=N;i++){
			if(!bas[i]&&i!=e) A[e][i]=A[l][i]/A[l][e];
		}
		A[e][l]=1.0/A[l][e];
	}
	int optimize(void){//最优化
		//返回1代表找到了解,返回0代表有无穷大的解
		while(true){
			int e=-1,l=-1;
			for(int i=1;i<=N;i++){
				if(!bas[i]){
					if(c[i]<=eps) continue;
					if(e==-1||c[i]>c[e]) e=i;
				}
			}
			if(e==-1) return 1;
			double delta=INF;
			for(int i=1;i<=N;i++){
				if(bas[i]){
					if(A[i][e]>eps&&delta>b[i]/A[i][e]){
						delta=b[i]/A[i][e];
						l=i;
					}
				}
			}
			if(delta==INF) return 0;
			Pivot(l,e);
		}
	}
};
Liner_Programming S;
int n,m;
bool init(void){
	if(scanf("%d%d",&n,&m)==EOF) return false;
	S.clear();
	S.N=n+m;
	//1~n:食物,n+1~n+m:人
	for(int i=n+1;i<=n+m;i++) S.bas[i]=true;
	for(int i=1;i<=n;i++) scanf("%lf",&S.c[i]);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++) scanf("%lf",&S.A[n+i][j]);
		scanf("%lf",&S.b[n+i]);
	}
	return true;
}
int main(){
	freopen("happiness.in","r",stdin);
	freopen("happiness.out","w",stdout);
	while(init()){
		S.optimize();
		printf("Nasa can spend %.0lf taka.\n",ceil(S.v*m));
	}
	return 0;
}