【UOJ#179】线性规划 单纯形

题目链接：

　　http://uoj.ac/problem/179

Solution

就是单纯形模板题，这篇博客就是存一下板子。

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define eps 1e-9

inline int read()

{

	int x=0,f=1; char ch=getchar();

	while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}

	while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}

	return x*f;

}

int N,M,id[11000];

double a[1100][1100],c[1100],b[1100],v,ans[1100];

inline void Pivot(int l,int e)

{

	swap(id[e],id[N+l]);

	double r=a[l][e];

	a[l][e]=1;

	for (int i=1; i<=N; i++) a[l][i]/=r;

	b[l]/=r;

	for (int i=1; i<=M; i++)

		if (i!=l) {

			r=a[i][e];

			a[i][e]=0,b[i]-=r*b[l];

			for (int j=1; j<=N; j++) a[i][j]-=r*a[l][j];

		}

	r=c[e];

	c[e]=0;

	for (int i=1; i<=N; i++) c[i]-=r*a[l][i];

	v+=r*b[l];

}

inline int Simplex()

{

	int l,e; double k;

	while (1) {

		l=e=0; k=-eps;

		for (int i=1; i<=M; i++)

			if (b[i]<k) k=b[i],l=i;

		if (!l) break;

		k=-eps;

		for (int i=1; i<=N; i++)

			if (a[l][i]<k && (!e || (rand()&1))) k=a[l][i],e=i;

		if (!e) {puts("Infeasible"); return 1;}

		Pivot(l,e);

	}

	while (1) {

		for (int i=1; i<=N; i++) {

			if (c[i]>eps) {e=i; break;}

			if (i==N) {printf("%.8lf\n",v); return 0;}

		}

		double re=1e18; l=0;

		for (int i=1; i<=M; i++)

			if (a[i][e]>eps && b[i]/a[i][e]<re)

				re=b[i]/a[i][e],l=i;

		if (!l) {puts("Unbounded"); return 2;}

		Pivot(l,e);

	}

}

int main()

{

	N=read(),M=read(); int type=read();

	for (int i=1; i<=N; i++) scanf("%lf",&c[i]),id[i]=i;

	for (int i=1; i<=M; i++) {

		for (int j=1; j<=N; j++) scanf("%lf",&a[i][j]);

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

	}

	int flag=Simplex();

	if (flag || !type) return 0;

	for (int i=1; i<=M; i++) ans[id[N+i]]=b[i];

	for (int i=1; i<=N; i++) printf("%.8lf ",ans[i]);

	return 0;

}