算法学习————高斯消元

其实高斯消元就和我们正常解方程一样，n个未知数，至少n个方程

整体代入法，每一个方程消去一个未知数，最后化成一个三角形

然后从最后一个方程把未知数一个一个解出来代入到前面的方程中

高斯消元步骤

高斯消元法在将增广矩阵化为最简形后对于自由未知量的赋值，需要掌握线性相关知识，且赋值存在人工经验的因素，使得在学习过程中有一定的困难，将高斯消元法划分为五步骤，从而提出五步骤法，内容如下：

1. 增广矩阵行初等行变换为行最简形；

2. 还原线性方程组；

3. 求解第一个变量；

4. 补充自由未知量；

5. 列表示方程组通解。

解的判断

无解：当消元完毕后，发现有一行系数都为 0，但是常数项不为 0，此时无解

多解：当消元完毕后，发现有多行系数、常数项均为 0，此时多解，有几行为全为 0，就有几个自由元，即变量的值可以任取，有无数种情况可以满足给出的方程组

看网上解析还有什么模线性方程组，异或方程组，可能没有机会学了吧

列主元：为了更好的保留精度，我们可以每次把绝对值最大的一行换上来

例题：[USACO10HOL]Driving Out the Piggies G

图上高斯消元也算是一类经典问题吧，好像树上可以不用，但是我还没有学

求每个点经过次数的概率：

设f[i]表示点i被经过的期望次数，值得注意的是最开始1号点就被经过了1次

\(f_i = \sum\limits_{(i,j)\in E} f_j\times \frac{1}{deg_j}\times (1-\frac{p}{q})\)

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#define B cout<<"Breakpoint"<<endl;
#define O(x) cout<<#x<<" "<<x<<endl;
#define o(x) cout<<#x<<" "<<x<<" ";
using namespace std;
int read(){
	int x = 1,a = 0;char ch = getchar();
	while (ch < ‘0‘||ch > ‘9‘){if (ch == ‘-‘) x = -1;ch = getchar();}
	while (ch >= ‘0‘&&ch <= ‘9‘){a = a*10+ch-‘0‘;ch = getchar();}
	return x*a;
}
const int maxn = 305;
int n,m,p,q;
int deg[maxn],edge[maxn][maxn];
double A[maxn][maxn],P;
void Gauss(int rowline,int colline,double a[][maxn]){
	for (int i = 1;i <= rowline;i++){
		int rowId = i;
		for (int j = i+1;j <= rowline;j++){
			if (fabs(a[j][i]) > fabs(a[rowId][i])) rowId = j;
		}
		if (rowId != i){
			for (int j = i;j <= colline+1;j++) swap(a[i][j],a[rowId][j]);
		}
		for (int j = i+1;j <= rowline;j++){
			double tmp = a[j][i]/a[i][i];
			for (int k = i;k <= colline+1;k++){
				a[j][k] -= a[i][k]*tmp;
			}
		}
	}
	for (int i = rowline;i >= 1;i--){
		for (int j = i+1;j <= colline;j++){
			a[i][colline+1] -= a[i][j]*a[j][colline+1];
		}
		a[i][colline+1] /= a[i][i];
	}
	for (int i = 1;i <= rowline;i++) printf("%.9lf\n",a[i][colline+1]*P);
}
int main(){
	n = read(),m = read(),p = read(),q = read();
	P = 1.0*p/q;
	for (int i = 1;i <= m;i++){
		int x = read(),y = read();
		edge[x][y] = 1,edge[y][x] = 1;
		deg[x]++,deg[y]++;
	}
	for (int i = 1;i <= n;i++){
		A[i][i] = 1.0;
		for (int j = 1;j <= n;j++){
			if (edge[i][j])	A[i][j] -= (1.0-P)/deg[j];
		}
	}
	A[1][n+1] = 1.0;
	Gauss(n,n,A);
	return 0;
}

算法学习————高斯消元

原文：https://www.cnblogs.com/little-uu/p/14978586.html