bzoj 3265: 志愿者招募加强版 （单纯形）

Description

Input

Output

Sample Input

Sample Output

HINT

Source

单纯形

题解：单纯形裸题啦

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#define N 1003#define M 10003#define eps 1e-7#define inf 1000000000using namespace std;double c[N],b[M],a[M][N],ans,v;int n,m;void PRiov(int l,int e){	b[l]/=a[l][e];	for (int i=1;i<=m;i++) 	 if (i!=e) a[l][i]/=a[l][e];	a[l][e]=1/a[l][e];	for (int i=1;i<=n;i++) 	 if (i!=l&&fabs(a[i][e])>eps) {	 	b[i]-=b[l]*a[i][e];	 	for (int j=1;j<=m;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<=m;i++)	 if (i!=e) c[i]-=c[e]*a[l][i];	c[e]=-c[e]*a[l][e];}double simple(){	int l,i,e;	double t;	while (1){		for (i=1;i<=m;i++) 		 if (c[i]>eps) break;		e=i;		if (e==m+1) return v;		t=inf;		for (int i=1;i<=n;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",&m,&n);	for (int i=1;i<=m;i++) scanf("%lf",&c[i]);    for (int i=1;i<=n;i++) {    	int k; scanf("%d",&k);    	for (int t=1;t<=k;t++) {    		int l,r; scanf("%d%d",&l,&r);    		for (int j=l;j<=r;j++) a[i][j]=1;		}		scanf("%lf",&b[i]);	}	ans=simple();	printf("%.0lf/n",ans);}