3112: [Zjoi2013]防守战线
Time Limit: 20 Sec Memory Limit: 512 MB Submit: 1420 Solved: 822 [Submit][Status][Discuss]
sol: 论单纯形的优越性
#include<cstdio> #include<algorithm> #include<string> #include<cstring> #include<cstdlib> #include<cmath> #include<iostream> using namespace std; int n,m; const double eps=1e-8; inline int read() { char c; int res,flag=0; while((c=getchar())>'9'||c<'0') if(c=='-')flag=1; res=c-'0'; while((c=getchar())>='0'&&c<='9') res=(res<<3)+(res<<1)+c-'0'; return flag?-res:res; } int l,e; double a[1100][11000]; double c[1100],d[11000]; double v=0; inline void povit() { c[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(fabs(a[i][e])>eps&&i!=l) { for(int j=1;j<=m;++j) if(j!=e) a[i][j]-=a[l][j]*a[i][e]; c[i]-=c[l]*a[i][e]; a[i][e]*=-a[l][e]; } v+=d[e]*c[l]; for(int i=1;i<=m;++i) if(i!=e) d[i]-=d[e]*a[l][i]; d[e]*=-a[l][e]; } inline double simplex() { while(true) { l=0;e=0; for(e=1;e<=m;++e) if(d[e]>eps) break; if(e==m+1) return v; double save=1e9; for(int i=1;i<=n;++i) if(a[i][e]>eps&&save>c[i]/a[i][e]) save=c[i]/a[i][e],l=i; if(save==1e9) return 1e9; povit(); } } int main() { // freopen("3112.in","r",stdin); // freopen(".out","w",stdout); n=read(); m=read(); for(int i=1;i<=n;++i) scanf("%lf",&c[i]); int l,r; for(int i=1;i<=m;++i) { l=read(); r=read(); for(int j=l;j<=r;++j) a[j][i]=1; scanf("%lf",&d[i]); } printf("%d",(int)(simplex()+0.5)); }