題目大意：

單純形*2。。

。

#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #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]<temp )temp=b[i]/A[i][e],l=i;if(temp==INF) return INF;Pivot(l,e);}} } int main() {using namespace Linear_Programming;int i,j,x,y,z;cin>>m>>n;for(i=1;i<=m;i++)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)<<endl;return 0; }

總結

以上是生活随笔為你收集整理的BZOJ 3112 Zjoi2013 防守战线 单纯形的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。