学了三天线性代数，基本把行列式和矩阵的一些基本的东西差不多都学明白了，然后就去学单纯形整整懵逼了一天最后终于懂了，线性规划好难啊QAQ。 都说这道题是单纯形裸题（都说单纯形只能用来做裸题23333），一直不懂，其实这道题是把问题转换成了一个对偶问题，因为这道题是要求一个最小化的函数值，所以我们把它转换成对偶问题，剩下的就是套一个单纯形的大板子了，感觉这个板子自己写难想，背还不好背，快哭了QAQ. 看来是我太傻了
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<cmath>using namespace std;const int N=1e3+5,M=1e4+5;const double eps=1e-7;const double inf=1e10;double A[N][M],B[N],c[M],ans;int n,m,L,R;inline void pivot(int l,int e){ B[l]/=A[l][e];//系数除以a的系数 for (int i=1;i<=n;++i) if (i!=e)A[l][i]/=A[l][e];//把a[e]的系数化为1，其他项除以其系数以约分 A[l][e]=1/A[l][e]; for (int i=1;i<=m;++i) if (i!=l&&fabs(A[i][e])>eps) { B[i]-=B[l]*A[i][e]; for (int j=1;j<=n;++j) if (j!=e)A[i][j]-=A[l][j]*A[i][e]; A[i][e]=-A[l][e]*A[i][e];//把l式带入其他式子，本质上是一个矩阵乘法 } ans+=c[e]*B[l]; for (int i=1;i<=n;++i) if (i!=e)c[i]-=c[e]*A[l][i]; c[e]=-c[e]*A[l][e];//把l式带入结果 }inline void simplex(){ int e; while(1) { for (e=1;e<=n;++e) if (c[e]>eps)break; //找到可行非基变量 if (e==n+1)break; double delta=inf,t;int l; for (int i=1;i<=m;++i)//寻找基变量 if (A[i][e]>eps&&(t=B[i]/A[i][e])<delta) { delta=t; l=i; } pivot(l,e); } }int main()//转换成对偶问题 { scanf("%d%d",&m,&n); for (int i=1;i<=m;++i) scanf("%lf",&B[i]); for (int i=1;i<=n;++i) { scanf("%d%d%lf",&L,&R,&c[i]); for (int j=L;j<=R;++j) A[j][i]=1; } simplex(); PRintf("%.0lf/n",ans);}新闻热点
疑难解答
