= =跟上一道基本相同，可以单纯形法解线性规划，也可以费用流. 写费用流的话建图就是一般的线性规划转费用流的套路，加上基变量，然后化成等式，每个下式减上式之后可以化成表示流量平衡的等式，然后根据等式建图就好了，跑一个最小费用最大流. 写单纯形没有写网络流好理解，单纯形的话因为这是最小化费用的，首先要转化成对偶问题（我到现在也不能理解对偶问题QAQ），我的理解就是把原本的B[i]写成c[i]，c[i]写成B[i]，n写成m，m写成n，然后xjb搞一搞就好了，而且本来也感觉单纯形这个模板凭理解很难打= =，其实背的话更难，因为背模板其实都是建立在理解的基础之上的，其实就是写的熟练罢了，不理解的话真的特别容易写错，跟自适应辛普森积分一样（捂脸），mdzz好的我承认我是数学不好.
#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,inf=1e10;double ans,A[M][N],B[M],c[N];int n,m,L,R;inline void pivot(int l,int e){ B[l]/=A[l][e]; for (int i=1;i<=n;++i) if (i!=e)A[l][i]/=A[l][e]; A[l][e]=1/A[l][e]; for (int i;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[i][e]*A[l][j]; A[i][e]=-A[l][e]*A[i][e]; } 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];}inline void simplex(){ int e; while(1) { for (e=1;e<=n;e++) if (c[e]>eps)break; if (e==n+1) break; double t,delta=inf;int l; for (int i=1;i<=m;++i) if (A[i][e]>eps&&(t=B[i]/A[i][e])<delta) l=i,delta=t; pivot(l,e); }}int main(){ cin>>n>>m; for (int i=1;i<=n;++i) scanf("%lf",&c[i]); for (int i=1;i<=m;++i) { scanf("%d%d%lf",&L,&R,&B[i]); for (int j=L;j<=R;++j) A[i][j]=1; } simplex(); PRintf("%.0lf",ans);}新闻热点
疑难解答
