今天中午竟然下雨了。
晚上回去补。
不就是一个 Θ ( n 2 ) \Theta(n^2) Θ(n2)大暴力吗？ 题目传送门： luogu P3389 \text{luogu P3389} luogu P3389【模板】高斯消元法。 贴一份代码吧。
#include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; int n; double a[110][110]; void gauss() { for(int i=1;i<=n;i++) { int p=i; for(int j=i+1;j<=n;j++) if(fabs(a[p][i])<fabs(a[j][i])) p=j; if(fabs(a[p][i])<1e-8) { printf("No Solution"); return; } for(int j=1;j<=n+1;j++) swap(a[i][j],a[p][j]); for(int j=i+1;j<=n;j++) { double d=a[j][i]/a[i][i]; for(int k=i;k<=n+1;k++) a[j][k]-=d*a[i][k]; } } for(int i=n;i>=1;i--) { for(int j=i+1;j<=n;j++) a[i][n+1]-=a[j][n+1]*a[i][j]; a[i][n+1]/=a[i][i]; } for(int i=1;i<=n;i++) printf("%.2lf\n",a[i][n+1]); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n+1;j++) scanf("%lf",&a[i][j]); gauss(); }一种神奇的操作。
uoj P179. \text{uoj P179.} uoj P179.线性规划。
已知 a , b , c a,b,c a,b,c三个数组。 我们得到了一些第 i i i条式子形如 ∑ j = 1 n a i j x j ≤ b i \sum_{j=1}^{n}a_{ij}x_{j}≤b_i ∑j=1naijxj≤bi约束条件。现在要找到 x j ≥ 0 x_j≥0 xj≥0的使 ∑ j = 1 n c j x j \sum_{j=1}^{n}c_jx_j ∑j=1ncjxj最大的解以及这个结果。
这个问题被称为线性规划。 高中必修书有讲，但上面是画图求解。 作为一名优秀的 oier \text{oier} oier，我们肯定要会打暴力 啊。 没错，这是一种极为优秀的暴力——单纯形法求解线性规划。
首先我们有标准式子，形如： max 5 x 1 + 4 x 2 + 3 x 3 s.t. 2 x 1 + 3 x 2 + x 3 ≤ 5 4 x 1 + x 2 + 2 x 3 ≤ 11 3 x 1 + 4 x 2 + 2 x 3 ≤ 8 x 1 , x 2 , x 3 ≥ 0 \begin{aligned}\max 5x_1+4x_2+3x_3\\ \text{s.t.} 2x_1+3x_2+x_3&≤5\\ 4x_1+x_2+2x_3&≤11\\ 3x_1+4x_2+2x_3&≤8\\ x_1,x_2,x_3≥0\end{aligned} max5x1+4x2+3x3s.t.2x1+3x2+x34x1+x2+2x33x1+4x2+2x3x1,x2,x3≥0≤5≤11≤8
− ( max ( − ( 5 x 1 + 4 x 2 + 3 x 3 ) ) ) = min ( 5 x 1 + 4 x 2 + 3 x 3 ) -\left(\max \left(-\left(5x_1+4x_2+3x_3\right)\right)\right)=\min(5x_1+4x_2+3x_3) −(max(−(5x1+4x2+3x3)))=min(5x1+4x2+3x3)
用 x ′ − x ′ ′ x'-x'' x′−x′′代替 x i x_i xi，其中 x ′ , x ′ ′ ≥ 0 x',x''≥0 x′,x′′≥0。
2 x 1 + 3 x 2 + x 3 = 5 2x_1+3x_2+x_3=5 2x1+3x2+x3=5
令 x 4 ≥ 0 x_4≥0 x4≥0，有： 2 x 1 + 3 x 2 + x 3 + x 4 ≥ 5 2x_1+3x_2+x_3+x_4≥5 2x1+3x2+x3+x4≥5
2 x 1 + 3 x 2 + x 3 ≥ 5 2x_1+3x_2+x_3≥5 2x1+3x2+x3≥5
两边同乘 − 1 -1 −1，得： → − 2 x 1 − 3 x 2 − x 3 ≤ − 5 →-2x_1-3x_2-x_3≤-5 →−2x1−3x2−x3≤−5
考虑将式子化为等式，有： z = max 5 x 1 + 4 x 2 + 3 x 3 s.t. 2 x 1 + 3 x 2 + x 3 − x 4 = 5 4 x 1 + x 2 + 2 x 3 − x 5 = 11 3 x 1 + 4 x 2 + 2 x 3 − x 6 = 8 x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ≥ 0 \begin{aligned}z=\max 5x_1+4x_2+3x_3\\ \text{s.t.} 2x_1+3x_2+x_3-x_4&=5\\ 4x_1+x_2+2x_3-x_5&=11\\ 3x_1+4x_2+2x_3-x_6&=8\\ x_1,x_2,x_3,x_4,x_5,x_6≥0\end{aligned} z=max5x1+4x2+3x3s.t.2x1+3x2+x3−x44x1+x2+2x3−x53x1+4x2+2x3−x6x1,x2,x3,x4,x5,x6≥0=5=11=8 这个操作称为松弛。
移一下项，有： z = − ( 5 x 1 + 4 x 2 + 3 x 3 ) s.t. x 4 = 5 − ( 2 x 1 + 3 x 2 + x 3 ) x 5 = 11 − ( 4 x 1 + x 2 + 2 x 3 ) x 6 = 8 − ( 3 x 1 + 4 x 2 + 2 x 3 ) x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ≥ 0 z=-(5x_1+4x_2+3x_3)\\ \begin{aligned}\text{s.t.} x_4&=5-(2x_1+3x_2+x_3)\\ x_5&=11-(4x_1+x_2+2x_3)\\ x_6&=8-(3x_1+4x_2+2x_3)\end{aligned}\\ x_1,x_2,x_3,x_4,x_5,x_6≥0 z=−(5x1+4x2+3x3)s.t.x4x5x6=5−(2x1+3x2+x3)=11−(4x1+x2+2x3)=8−(3x1+4x2+2x3)x1,x2,x3,x4,x5,x6≥0
对于左边这些新加进来的变量，我们称为基变量；右边这些旧的变量，我们称为非基变量。
开始求解了。 做法就是：令这些非基变量为 0 0 0，就得到了基本可行解： { x 1 , x 2 , x 3 , x 4 , x 5 , x 6 } = { 0 , 0 , 0 , 5 , 11 , 8 } \{x_1,x_2,x_3,x_4,x_5,x_6\}=\{0,0,0,5,11,8\} {x1,x2,x3,x4,x5,x6}={0,0,0,5,11,8}。 许多时候，这已经是 x x x的一组解，尽管不一定是最有的。 但是有例外： max x 1 + x 2 s.t. x 1 + 3 x 2 ≤ − 2 x 1 , x 2 ≥ 0 \max x_1+x2\\ \begin{aligned}\text{s.t.}x_1+3x_2≤-2 \end{aligned}\\ x_1,x_2≥0 maxx1+x2s.t.x1+3x2≤−2x1,x2≥0
z = − ( x 1 + x 2 ) s.t. x 3 = − 2 + ( x 1 + 3 x 2 ) x 1 , x 2 ≥ 0 z=-(x_1+x2)\\ \begin{aligned}\text{s.t.}x_3=-2+(x_1+3x_2) \end{aligned}\\ x_1,x_2≥0 z=−(x1+x2)s.t.x3=−2+(x1+3x2)x1,x2≥0 当 x 1 , x 2 = 0 x_1,x_2=0 x1,x2=0时，有： { x 1 , x 2 , x 3 } = { 0 , 0 , − 2 } \{x_1,x_2,x_3\}=\{0,0,-2\} {x1,x2,x3}={0,0,−2}。 此时不合法。
为什么不合法？ 我们发现 b i < 0 b_i<0 bi<0时存在不合法方案（例子中的 − 2 < 0 -2<0 −2<0）。 此时我们就要判断是否有解。 若 b i < 0 b_i<0 bi<0，找到一个 a j < 0 a_j<0 aj<0，转换它们，不断重复直到所有的 b i b_i bi都大于 0 0 0。 若最后无法使所有的 b i > 0 b_i>0 bi>0（即当前 b i < 0 b_i<0 bi<0时无法找到 a j < 0 a_j<0 aj<0），那么无解。 转换的过程可以用高斯消元。
