免费网站如何做推广方案,wordpress公众号推送,wordpress熊掌认证,怎么增加网站的流量正题
题目链接:https://www.luogu.com.cn/problem/P3337 题目大意 nnn个地方可以建立塔也可以不建立塔#xff0c;第iii个位置建立需要消耗CiC_iCi元 mmm个限制要求在某个区间内的塔的数量超过DiD_iDi 1≤n≤1000,1≤m≤100001\leq n\leq 1000,1\leq m\leq 100001≤n≤10…正题
题目链接:https://www.luogu.com.cn/problem/P3337 题目大意
nnn个地方可以建立塔也可以不建立塔第iii个位置建立需要消耗CiC_iCi元
mmm个限制要求在某个区间内的塔的数量超过DiD_iDi
1≤n≤1000,1≤m≤100001\leq n\leq 1000,1\leq m\leq 100001≤n≤1000,1≤m≤10000 题目大意
抽象成数学模型的话 minimize∑i1nCiximinimize\ \ \sum_{i1}^nC_ix_iminimize i1∑nCixi ∑lirixi,j≥Di\sum_{l_i}^{r_i}x_{i,j}\geq D_ili∑rixi,j≥Di 然后网络流好像草不过去考虑点线性规划玄学算法
先把它对偶了 maximize∑i1nDiximaximize\ \ \sum_{i1}^nD_ix_imaximize i1∑nDixi ∑lirixi,j≤Ci\sum_{l_i}^{r_i}x_{i,j}\leq C_ili∑rixi,j≤Ci
然后就是一个裸的单纯形了。
所以单纯形是什么这里就粗略的讲一下。 我是看线性规划与单纯形算法-吴一凡的课件学的
对于普通的松弛型有三个限制
对于每个iii满足∑j1nAi,jxjxnibi\sum_{j1}^nA_{i,j}x_jx_{ni}b_i∑j1nAi,jxjxnibixni≥0x_{ni}\geq 0xni≥0最大化∑i1nxici\sum_{i1}^nx_ic_i∑i1nxici
定义所有的xnix_{ni}xni为基变量xi(i≤n)x_i(i\leq n)xi(i≤n)为非基变量
然后单纯形的流程就是先找出任意一个cic_ici为正的基变量xpx_pxp
然后去掉所有其他非基变量后得到一个对于xpx_pxp最小的限制即最小的cpap,z\frac{c_p}{a_{p,z}}ap,zcp
然后考虑交换非基变量xpx_pxp和基变量xznx_{zn}xzn此时可以得到一个由第zzz行的式子推出的关于xpx_pxp的式子带入回到需要最大化的式子当中。此时由于cic_ici为正所以式子中会有一个正的常数。
此时这个常数就相当于大化了那个式子不停重复上面的转轴操作直到无法找到正的cic_ici为止此时就代表无法继续扩大了
这个是实数的但是我们这题的要求是整数但是我们这里的约束矩阵AAA是一个全幺模矩阵所以至少保证有一组最优解全是整数又不用输出方案直接单纯形暴艹就可以了
复杂度比较玄学但是能过这题 code
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const int N1100;
const double eps1e-8,inf1e9;
int n,m;double c[N],w[N*10],a[N][N*10],ans;
void Pivot(int l,int e){c[l]/a[l][e];for(int i1;im;i)if(i!e)a[l][i]/a[l][e];a[l][e]1.0;for(int i1;in;i)if(i!lfabs(a[i][e])eps){c[i]-a[i][e]*c[l];for(int j1;jm;j)if(j!e)a[i][j]-a[i][e]*a[l][j];a[i][e]-a[i][e]*a[l][e];}answ[e]*c[l];for(int i1;im;i)if(i!e)w[i]-w[e]*a[l][i];w[e]-w[e]*a[l][e];
}
double simplex(){while(1){double minsinf;int i0,j0,k0;for(j1;jm;j)if(w[j]eps)break;if(jm)return ans;for(i1;in;i)if(a[i][j]epsminsc[i]/a[i][j])ki,minsc[i]/a[i][j];if(minsinf)return inf;Pivot(k,j);}
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%lf,c[i]);for(int i1;im;i){int l,r;scanf(%d%d%lf,l,r,w[i]);for(int jl;jr;j)a[j][i]1.0;}printf(%d\n,(int)(simplex()0.5));return 0;
}
